Practice/Apple/Leetcode 1209. Remove All Adjacent Duplicates in String II

Leetcode 1209. Remove All Adjacent Duplicates in String II

CodingMust

Problem

You are given a string s and an integer k. Your task is to repeatedly remove any sequence of exactly k consecutive identical characters from the string until no more such sequences exist.

The removal process continues until the string stabilizes—meaning no sequence of k identical consecutive characters remains. When characters are removed, the remaining parts of the string merge together, which may create new sequences of k consecutive identical characters that must also be removed.

Return the final string after all possible removals have been completed.

Requirements

1. Remove exactly k consecutive identical characters in each operation
2. Continue removing until no sequence of k identical consecutive characters exists
3. Handle cascading removals where merging creates new removable sequences
4. Return the final stabilized string (may be empty)

Constraints

• 1 ≤ s.length ≤ 105
• 2 ≤ k ≤ 104
• s contains only lowercase English letters
• Expected time complexity: O(n) where n is the length of the string
• Expected space complexity: O(n)

Examples

Example 1:

` Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation:

• First pass: "deeedbbcccbdaa" → remove "eee" and "ccc" → "ddbbbdaa"
• Second pass: "ddbbbdaa" → remove "bbb" → "dddaa"
• Third pass: "dddaa" → remove "ddd" → "aa"
• No more sequences of 3 consecutive identical characters `

Example 2:

Input: s = "abcd", k = 2 Output: "abcd" Explanation: No character appears k=2 times consecutively, so nothing is removed

Example 3:

` Input: s = "aaabbb", k = 3 Output: "" Explanation:

• First pass: remove "aaa" → "bbb"
• Second pass: remove "bbb" → "" `