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"`
Overview: This question evaluates proficiency in string manipulation, algorithmic thinking, and efficient use of data structures for handling contiguous character groups and iterative reductions.
Read the full Attentive Software Engineer interview experience this question came from
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.