Problem Breakdown
We are given a string s and an integer k. The core operation is removing any contiguous block of exactly k identical characters. Crucially, this removal causes the left and right sides to concatenate immediately. We repeat this process until no more blocks of size k exist consecutively in the remaining string.
Inputs:
s: A string consisting of lowercase English letters (length up to ).k: An integer representing the duplicate threshold ().
Outputs:
- The final resulting string after all possible removal operations.
Implicit Constraints & Edge Cases:
- Concatenation Effectiveness: Removing a block might bring two previously separated characters together, potentially forming new removable groups (e.g.,
d+ removed group +d). Our logic must handle this “chain reaction.” - Large k: If the remaining string length is less than
k, no further removals are possible. - Empty Result: It’s theoretically possible for all characters to be deleted, resulting in an empty string (though constraints usually imply a valid non-empty output or we return "").
Intuition
A naive approach would scan the string repeatedly: find adjacent duplicates, slice them out using Python slicing (s[:i] + s[i+k:]), and repeat. While this is easy to implement mentally, it suffers from high complexity because every deletion involves creating a new string object proportional to its length (). In worst-case scenarios (e.g., aaaa...a, ), we might perform deletions that cascade frequently, leading to an overall time complexity of roughly . Given the constraint , this will Time Out.
The key insight is recognizing this as a Stack problem similar to “Remove All Adjacent Duplicates In String” (LeetCode 1047). Instead of physically deleting characters from a mutable string, we can build our result incrementally using a stack that tracks the current run length of each character. When adding a new character matches the top of the stack:
- Increment its count.
- If the count reaches
k, pop it entirely (simulating deletion).
This implicitly handles concatenation because if we remove characters from the middle, the next incoming character is compared against whatever remains at the top of our logical “remaining string” structure on the stack. This reduces complexity to linear time .
Approach
- Initialize: Create an empty list
stackthat will store tuples(character, count). We use a tuple because we need to track how many consecutive instances of a character are currently adjacent in our result buffer. (Note: The implementation uses lists[char, 1]for mutability during the loop). - Iterate: Loop through each character
cin the input strings. - Check Top: Look at the top element of the stack (if it exists).
- If the current char
cmatches the character stored on the stack: Increment the count associated with that character. Check if this new count equalsk.- If yes (
count == k): Pop the tuple from the stack entirely, as these characters are removed.
- If yes (
- If they do not match (or stack is empty): Push a new tuple
(c, 1)onto the stack.
- If the current char
- Reconstruct: After processing all input characters, iterate through the remaining tuples in
stack. For each character and its count, append that many instances of the character to our result string using list comprehension or join logic.
Complexity Analysis
- Time Complexity: where is the length of
s. We traverse the input string exactly once (). Stack operations (push/pop) are amortized . The final reconstruction iterates over at most characters. Total time is linear. - Space Complexity: in the worst case where no deletions occur, requiring storage for all input characters plus the output string construction buffer.
Solution
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
# Stack stores lists of [character, current_consecutive_count]
# Lists are used to allow in-place mutation of count before popping if needed.
stack = []
for char in s:
if stack and stack[-1][0] == char:
# If top matches current character, increment count
stack[-1][1] += 1
# If the consecutive count reaches k, remove from stack (pop)
if stack[-1][1] == k:
stack.pop()
else:
# Push new character with initial count of 1
stack.append([char, 1])
# Reconstruct string from remaining elements in the stack
return "".join(char * count for char, count in stack)
Edge Cases Handled
- No Duplicates: If no sequence reaches length
k, the