Remove Repeated Character Groups
Company: Attentive
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a string `s` and an integer `k`.
Repeatedly remove any contiguous group of `k` identical characters. After a removal, the remaining parts of the string are concatenated, which may create new removable groups. Continue until no more removals are possible, and return the final string.
As a warm-up, explain how you would solve the special case `k = 3`, then generalize the approach to any `k`.
Constraints:
- `1 <= len(s) <= 100000`
- `2 <= k <= 100000`
- `s` contains lowercase English letters
Example:
- Input: `s = "abbbaaac"`, `k = 3`
- Output: `"c"`
Quick Answer: This question evaluates proficiency in string manipulation, algorithmic thinking, and efficient use of data structures for handling contiguous character groups and iterative reductions.
You are given a lowercase string `s` and an integer `k`.
Repeatedly remove any contiguous group of **at least** `k` identical characters. After a removal, the remaining parts of the string are concatenated, which may create new removable groups. Continue until no more removals are possible, and return the final string.
Warm-up: first think about the special case `k = 3`. If a middle group disappears, two groups on its left and right may become adjacent and merge into a new removable group. Then generalize the same idea to any `k`.
Example: `s = "abbbaaac"`, `k = 3`
- Remove `bbb` -> `aaaa c`
- Now `aaaa` is a group of length 4, which is at least 3, so remove it
- Final result: `"c"`
Constraints
- 1 <= len(s) <= 100000
- 2 <= k <= 100000
- s contains only lowercase English letters
Examples
Input: ("abbbaaac", 3)
Expected Output: "c"
Explanation: Remove `bbb` first, producing `aaaac`. The `aaaa` run has length 4, which is at least 3, so it is also removed. Only `c` remains.
Input: ("a", 2)
Expected Output: "a"
Explanation: A single character cannot form a removable group.
Hints
- For the warm-up `k = 3`, think in terms of runs of equal characters rather than individual characters. Removing one run can cause neighboring runs to merge.
- A stack of `[character, count]` pairs lets you track the compressed string built so far. When a merged run reaches length at least `k`, delete that whole run.