608. Remove All Adjacent Duplicates in String II
You are given a string s of lowercase English letters and an integer k. Whenever k copies of the same letter sit side by side in s, that whole group may be erased; the rest of the string closes up around the gap — which can bring two identical letters together and form a brand-new group of k.
Keep erasing groups until no k equal adjacent letters remain anywhere, and return the string that is left. The leftover string is the same no matter which order the erasures happen in, so the answer is unique (it may be empty).
Example 1:
Input: s = "abcd", k = 2
Output: "abcd"
Explanation: No letter ever appears twice in a row, so nothing can be erased.
Example 2:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: Erase "eee" → "ddbbcccbdaa". Erase "ccc" → "ddbbbdaa". That created "bbb" — erase it → "dddaa". That created "ddd" — erase it → "aa".
Example 3:
Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
Explanation: Every doubled letter collapses in a chain until only "ps" survives.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- 2 ≤ k ≤ 10⁴
- s consists of lowercase English letters only.
Hints:
Erasing a group can create a new group that starts *before* the point you were looking at. Simulating with rescans works, but ask yourself what information a rescan recomputes that you already knew.
Walk the string once with a stack whose entries are pairs (character, run length). When the top run's length reaches k, pop it — the run underneath is now adjacent to whatever comes next, so the cascade is handled automatically.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abcd", k = 2
Expected output: "abcd"