This article describes the question from Day 16 of the 30 Days of Code competition hosted by Geeks for Geeks.

Question

Given a string S and an integer K, the task is to reduce the string by applying the following operation: Choose a group of K consecutive identical characters and remove them. The operation can be performed any number of times until it is no longer possible.

Example 1:

Input: K = 2 S = "geeksforgeeks" Output: gksforgks Explanation: Modified String after each step: "geegsforgeeks" -> "gksforgks"

Example 2:

Input: K = 2 S = "geegsforgeeeks" Output: sforgeks Explanation: Modified String after each step: "geegsforgeeeks" -> "ggsforgeks" -> "sforgeks"

Your Task:
You don't need to read input or print anything. Complete the function Reduced_String() which takes integer K and string S as input parameters and returns the reduced string.

Expected Time Complexity: O(|S|) Expected Auxiliary Space: O(|S|)

Constraints: 1 ≤ |S| ≤ 105 1 ≤ K ≤ |S|

Solution

import re
class Solution:
    def Reduced_String(self, k, s):
        regex = '([a-z])'+'\\1'+'{'+"{}".format(k-1)+'}'
        for i in range(1,len(s)//2):
            r = re.sub(regex,"",s)
            if len(s) == len(r):
                break
            s = r
        return s

First, we import re. This library allows us to perform regular expression operations. The one we rely on here is sub. This substitutes each occurrence of an existing pattern with another string. The regular expression pattern regex will substitute any adjacent elements that are equal (i.e, 'ee') with an empty string (i.e., ''). This is effectively removing them from the string.

We repeat this process as many times as it is physically possible. This is until the length of the string does not change after a substitution. That is the break condition of our loop. We assign the previous value of r to s, and compute the next substitution and store that value in r. This way we have a reference to the string before and after substitution.

Our loop has a break condition so that it does not perform excess computations. Once the string is no longer being modified, there is no point continuing to iterate through the loop. Finally, once the loop has been exhausted, we return s. The string after the maximum number of concatenations has been performed.