⚡Flashcard Drill➔
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

  1. Store (character, count) pairs on a stack instead of individual characters.
  2. When the current character matches the top, increment its count; if the count reaches k, pop the entry.
  3. Because a run can span a removal boundary, the run-length representation is essential -- a plain character stack would need a rescan.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems