Remove All Adjacent Duplicates in String II
Asked at Salesforce
Problem
Given a string s and an integer k, remove k adjacent identical characters repeatedly until no more removals are possible. Return the final string after all possible removals have been performed.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | MEDIUM | View all Salesforce questions → |
How to Think About It
Brute force: scan the string repeatedly and remove k adjacent duplicates until no changes occur.
Use a stack to store characters along with their consecutive counts.
When pushing a character, check if it matches the top of the stack.
If it matches, increment the count at the top; if count reaches k, pop that entry.
If it does not match, push the character with count 1 onto the stack.
Optimal Approach
Use a stack where each element stores a character and its consecutive count. Iterate through the string: if the current character equals the top of the stack, increment the count; otherwise push a new entry with count 1. Whenever a count reaches k, pop that entry. After processing the entire string, reconstruct the result by repeating each character in the stack by its count. This runs in O(n) time and O(n) space.
What Trips People Up in Real Interviews
Clarify whether removals cascade (yes, they do).
Mention that a single pass with a stack is optimal.
Discuss edge cases: entire string removed, no removals needed.
Explain why a naive string-builder approach is O(n*k) worst case.
Talk about reconstructing the result from the stack efficiently.
Solution Code
def removeDuplicates(s, k):
stack = []
for c in s:
if stack and stack[-1][0] == c:
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
else:
stack.append([c, 1])
return ''.join(c * cnt for c, cnt in stack)Frequently Asked Questions
What is the Remove All Adjacent Duplicates in String II problem?
Given a string s and an integer k, remove k adjacent identical characters repeatedly until no more removals are possible. Return the final string after all possible removals have been performed.
How do you solve Remove All Adjacent Duplicates in String II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Remove All Adjacent Duplicates in String II?
Remove All Adjacent Duplicates in String II is asked at Salesforce. It is a medium difficulty problem.
What are common mistakes on Remove All Adjacent Duplicates in String II?
- Clarify whether removals cascade (yes, they do).
- Mention that a single pass with a stack is optimal.
- Discuss edge cases: entire string removed, no removals needed.
- Explain why a naive string-builder approach is O(n*k) worst case.
- Talk about reconstructing the result from the stack efficiently.