Remove runs of length at least k
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string s and an integer k (k >=
2), repeatedly remove every maximal contiguous group of the same character whose length is at least k, deleting the entire group (not just a chunk of size k). After each deletion, the remaining parts of the string collapse together and the process continues until no more deletions are possible. Return the final string.
Examples:
- s = 'abbbbc', k = 3 -> remove 'bbbb' -> 'ac'.
- s = 'aaabbbcc', k = 3 -> remove 'aaa' and 'bbb' -> 'cc'.
- s = 'baaabbbaac', k = 3 -> remove 'aaa' and 'bbb' -> 'bc' (no further deletions).
Design an algorithm that runs in O(n) time and O(n) space using a stack-based approach (character + run length), and explain how you detect new removable runs formed after collapses.
Quick Answer: This question evaluates string manipulation, run-length detection, and algorithmic efficiency, focusing on tracking and removing maximal contiguous character groups. It is commonly asked in the Coding & Algorithms domain to assess practical application–level skills in designing linear-time, linear-space implementations that handle dynamic sequence collapses using appropriate data structures.
Given a string `s` and an integer `k` (k >= 2), repeatedly remove every maximal contiguous group (run) of the same character whose length is **at least** k, deleting the **entire** group (not just a chunk of size k). After each deletion the remaining parts of the string collapse together, which may form **new** removable runs, so the process continues until no more deletions are possible. Return the final string.
This is a one-dimensional "candy crush" variant. The subtlety vs. the classic *Remove All Adjacent Duplicates II* problem: you delete the whole run when its length reaches k, not exactly k characters. For example with k = 3, `abbbbc` removes all four `b`s (`bbbb`) and becomes `ac`, not `abc`.
Examples:
- `s = 'abbbbc', k = 3` -> remove `bbbb` -> `'ac'`.
- `s = 'aaabbbcc', k = 3` -> remove `aaa` and `bbb` -> `'cc'`.
- `s = 'baaabbbaac', k = 3` -> remove `aaa` and `bbb`; the surviving `b`, `aa`, `c` collapse to `'baac'` (the remaining run of `aa` has length 2 < 3, so no further deletion).
Aim for an efficient solution and be ready to explain how deletions can cascade after a collapse merges two equal runs on either side of a removed group.
Constraints
- 0 <= len(s) <= 10^5
- s consists of lowercase English letters
- 2 <= k <= len(s) (when len(s) >= 2); for very short strings k may exceed len(s), in which case nothing is removed
- Return the empty string if everything is removed
Examples
Input: ('abbbbc', 3)
Expected Output: 'ac'
Explanation: The single run 'bbbb' has length 4 >= 3, so the whole group is removed, leaving 'a' + 'c' = 'ac'.
Input: ('aaabbbcc', 3)
Expected Output: 'cc'
Explanation: 'aaa' (len 3) and 'bbb' (len 3) are both removed; 'cc' (len 2 < 3) remains.
Hints
- First reduce the input to a list of runs: consecutive (character, count) pairs. A run is removable iff count >= k.
- The hard part is the cascade: after you delete a run, the run to its left and the run to its right become adjacent. If they are the same character, they merge into one larger run whose new length might now be >= k, triggering another deletion — which can chain further left or right.
- A correct-and-simple model is to repeatedly scan the string, dropping every maximal run with length >= k, and rebuild until a full pass makes no change. This is easy to reason about and matches the definition exactly.
- For O(n): use a stack of (char, count). For each incoming character, increment the top's count if it matches, else push (char, 1). When a top's count reaches k, pop it; then if the new top's character equals the next character you append, they merge — re-check the merged count against k to cascade. Be careful that a removal can also let the element below merge upward.
- Watch the boundary: removing the entire run means a run of length 5 with k = 3 disappears completely, not down to length 2 (5 - 3). Don't confuse this with 'remove exactly k duplicates'.