NeetCode #361LC-1209MediumStack
← Back to All Problems#361 · #1209 · Remove All Adjacent Duplicates in String II(删除字符串中的所有相邻重复项 II)
📌 Problem Statement & Constraints
Given a string
s and an integer k, repeatedly delete k adjacent equal characters until no more deletions are possible, and return the final string. Constraints: 1 <= s.length <= 10^5, 1 <= k <= 10^4.💡 Core Algorithmic Approaches
- Store
(character, count)pairs on a stack instead of individual characters. - When the current character matches the top, increment its count; if the count reaches
k, pop the entry. - Because a run can span a removal boundary, the run-length representation is essential -- a plain character stack would need a rescan.
- The answer is the stack expanded back into a string.
💻 Benchmark Python3 Implementation
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
st = [] # entries are [char, count]
for ch in s:
if st and st[-1][0] == ch:
st[-1][1] += 1
if st[-1][1] == k:
st.pop() # the run reached k -> delete it
else:
st.append([ch, 1])
return "".join(ch * cnt for ch, cnt in st)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each character is processed once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Using a plain character stack: after a removal, runs that merge across the deletion would not be detected without rescanning.
- Popping when the count exceeds
k: the check is exactly== k, since the count grows by one at a time. - Forgetting that a removal can merge two runs: the run-length representation handles this implicitly, because the merged run is simply the entry below.
- Rescanning the string until stable: O(n^2) and unnecessary.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.