Problem Explanation

The problem gives a string s and an integer k. The task is to repeatedly delete substrings of length k that consist of the same character until no such substrings exist, and then return the string s after all deletions are made.

The deletions work as follows: when k adjacent characters in the string are the same, they are all deleted. This causes the left and right parts of the string to be concatenated together. The process is repeated until no more deletions can be made.

For example, given the string s = "deeedbbcccbdaa", and k = 3. Here,

• First, we delete "eee" and "ccc", and end up with "ddbbbdaa"
• Next, we delete "bbb", and now we have "dddaa".
• Finally, we delete "ddd", and the final string is "aa".

Approach

The solution for this problem can be approached using a stack data structure. A pair of character and count is kept in the stack. When iterating through the string s, for every character, a check is done to see whether the current character is same as on top of stack.

Depending on that, either a new pair of character and count is pushed to stack, or the count of top stack character is incremented until it equals k. Once the count reaches k, that character pair is popped from the stack. Finally, the stack contents are used to construct the final string.

Let's illustrate the approach with an example

Consider the string s = "deeedbbcccbdaa", and k = 3,

Iteration 1: s = "d"

• The current char c is "d".
• The stack is empty, a new pair of character and count: (d, 1) is pushed to the stack.

Iteration 2: s = "de"

• The current char c is "e".
• The top character of stack is not "e". Thus, a new pair of character and count (e, 1) is pushed to the stack.

Iteration 3: s = "dee"

• The current char c is "e".
• The top character of stack is "e". Thus, the count of "e" in stack is incremented to 2.

Iteration 4: s = "deee"

• The current char c is "e".
• Top character of stack is "e". Hence, count of "e" in stack is incremented to 3.
• Check whether count of "e" equals k. Since they are equal, we pop (e, 3) from the stack.

The rest of the string will be processed in a similar manner. At the end, the final string is constructed using the characters and counts left in the stack.

Solutions

Python

1
2python
3class Solution:
4    def removeDuplicates(self, s: str, k: int) -> str:
5        stack = []
6        for c in s:
7            # If stack is not empty and current character equals to the last character in stack
8            if stack and stack[-1][0] == c:
9                stack[-1][1] += 1
10                # If count of last character equals to k, remove it from stack
11                if stack[-1][1] == k:
12                    stack.pop()
13            # If stack is empty or current character not equals to the last character in stack
14            else:
15                stack.append([c, 1])
16        return "".join(c * count for c, count in stack)

Java

1
2java
3class Solution {
4    public String removeDuplicates(String s, int k) {
5        // Stack for storing pair character and count
6        ArrayList<Pair<Character,Integer>> stack = new ArrayList<Pair<Character,Integer>>();
7        for (char c : s.toCharArray()) {
8            if (!stack.isEmpty() && stack.get(stack.size()-1).getKey() == c) {
9                stack.get(stack.size() - 1).setValue(stack.get(stack.size() - 1).getValue() + 1);
10                if (stack.get(stack.size() - 1).getValue() == k) {
11                    stack.remove(stack.size() - 1);
12                }
13            } else {
14                stack.add(new Pair(c, 1));
15            }
16        }
17        StringBuilder ans = new StringBuilder();
18        for (Pair<Character, Integer> pair : stack) {
19            for (int i = 0; i < pair.getValue(); i++) {
20                ans.append(pair.getKey());
21            }
22        }
23        return ans.toString();
24    }
25}

JavaScript

1
2javascript
3class Solution {
4    removeDuplicates(s, k) {
5        const stack = [];
6        for (let c of s) {
7            if (stack.length && stack[stack.length - 1][0] === c) {
8                stack[stack.length - 1][1] += 1;
9                if (stack[stack.length - 1][1] === k) {
10                    stack.pop();
11                }
12            } else {
13                stack.push([c, 1]);
14            }
15        }
16        return stack.map(([c, count]) => c.repeat(count)).join("");
17    }
18}

C++

1
2cpp
3class Solution {
4public:
5    string removeDuplicates(string s, int k) {
6        vector<pair<char, int>> stack;
7        for (char c : s) {
8            if (stack.empty() || stack.back().first != c) {
9                stack.push_back({c, 1});
10            } else if (++stack.back().second == k) {
11                stack.pop_back();
12            }
13        }
14        string ans;
15        for (auto& [c, count] : stack) {
16            ans.append(count, c);
17        }
18        return ans;
19    }
20};

C#

1
2csharp
3public class Solution {
4    public string RemoveDuplicates(string s, int k) {
5        var stack = new List<(char, int)>();
6        foreach (var c in s) {
7            if (stack.Count > 0 && stack[stack.Count - 1].Item1 == c) {
8                stack[stack.Count - 1] = (c, stack[stack.Count - 1].Item2 + 1);
9                if (stack[stack.Count - 1].Item2 == k) {
10                    stack.RemoveAt(stack.Count - 1);
11                }
12            } else {
13                stack.Add((c, 1));
14            }
15        }
16        var ans = new StringBuilder();
17        foreach (var pair in stack) {
18            ans.Append(new string(pair.Item1, pair.Item2));
19        }
20        return ans.ToString();
21    }
22}

Conclusion

This problem is a classical example of handling complicated rules. The key here is to first identify what data structure will be most effective for our case. Then, we construct the solution logic based on how the elements should be manipulated within this data structure - in this case, a stack.

This problem particularly exemplifies the LL(k) (Left-to-right, Leftmost derivation) language parsing property, where we keep track of k characters at a time. The "deletion" of repeated character sequences is essentially recognizing "patterns" in our string and removing them to simplify our final output. The stack happened to be our tool of choice here due to its LIFO (last-in, first-out) nature which is suitable for such string manipulation problems.

On a closing note, handling stack data structure and being able to abstract problems into the world of stacks, trees, and graphs are critical in going a long way in coding interview and development scenarios. Keep practicing more problems to get a solid understanding of these concepts. Happy coding!