Remove Adjacent Duplicate Runs of Length K

Question

Given a string, the task is to remove all adjacent duplicate characters that appear consecutively K times.

Codemia · Accepted Answer

To solve the problem of removing adjacent duplicates of length K, we can utilize a stack data structure. The idea is to traverse the string and keep track of consecutive characters along with their counts. Whenever we reach K duplicates, we can remove them from the stack.

1. Initialize an empty stack.
2. Traverse each character in the string:
   - If the stack is not empty and the top of the stack is the same as the current character, increment the count.
   - If the count reaches K, pop the character from the stack.
   - If the current character is different, push it onto the stack with a count of 1.
3. Construct the final string from the stack.

The time complexity of this algorithm is O(n), where n is the length of the string, since we are making a single pass through the string. The space complexity is O(n) in the worst case, where no duplicates exist.

```python
def remove_adjacent_duplicates(s: str, k: int) -> str:
    stack = []
    for char in s:
        if stack and stack[-1][0] == char:
            stack[-1][1] += 1
            if stack[-1][1] == k:
                stack.pop()
        else:
            stack.append([char, 1])
    return ''.join(char * count for char, count in stack)
```

Consider edge cases such as:
- An empty string, which should return an empty string.
- A string where no characters repeat K times, which should return the original string.
- A string where all characters are the same and equal to K, which should return an empty string.

Remove Adjacent Duplicate Runs of Length K

Attentive

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Attentive Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string