How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Remove runs of length at least k | Meta Coding Question

Quick Overview

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.

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.

Input: ('baaabbbaac', 3)

Expected Output: 'baac'

Explanation: Remove 'aaa' and 'bbb'. The surviving pieces 'b', 'aa', 'c' collapse to 'baac'; the 'aa' run has length 2 < 3, so no further deletion.

Input: ('deeedbbcccbdaa', 3)

Expected Output: 'aa'

Explanation: Cascade: remove 'eee' -> the two 'd's around it merge; remove 'ccc' -> the two 'b's around it merge to 'bbb' -> remove it -> now three 'd's are adjacent -> remove 'ddd'. The trailing 'aa' (len 2) stays.

Input: ('pbbcggttciiippooaais', 2)

Expected Output: 'pis'

Explanation: With k=2 every run of length >= 2 is stripped, cascading repeatedly until only the isolated single characters 'p', 'i', 's' survive (the 'iii' becomes empty, but the 'p...s' tail and the leading 'p' remain as singletons after collapses).

Input: ('', 2)

Expected Output: ''

Explanation: Empty input: nothing to remove.

Input: ('a', 2)

Expected Output: 'a'

Explanation: A single character cannot form a run of length >= 2.

Input: ('aaaa', 2)

Expected Output: ''

Explanation: One run of length 4 >= 2 is removed entirely, leaving the empty string.

Input: ('abcabc', 3)

Expected Output: 'abcabc'

Explanation: No two adjacent characters are equal, so no run reaches length 3; the string is unchanged.

Input: ('aabbaabb', 2)

Expected Output: ''

Explanation: Remove 'aa','bb','aa','bb' (all len 2). After they vanish there is nothing left; result is empty.

Input: ('abbabbbba', 2)

Expected Output: ''

Explanation: k=2 cascade: remove 'bb' -> 'aabbbba' wait/collapse merges; iterating removes every >=2 run until the whole string is consumed, yielding empty.

Input: ('cccacbaaaabbbbbca', 4)

Expected Output: 'cccacbca'

Explanation: Only runs of length >= 4 go: 'aaaa' (len 4) and 'bbbbb' (len 5) are removed; the surrounding singletons collapse to 'cccacb' + 'ca' = 'cccacbca' (the leading 'ccc' has length 3 < 4 so it stays).

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'.

Last updated: Jun 26, 2026

Loading coding console...

Quick Overview

Remove runs of length at least k

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

Input: ('baaabbbaac', 3)

Expected Output: 'baac'

Explanation: Remove 'aaa' and 'bbb'. The surviving pieces 'b', 'aa', 'c' collapse to 'baac'; the 'aa' run has length 2 < 3, so no further deletion.

Input: ('deeedbbcccbdaa', 3)

Expected Output: 'aa'

Input: ('pbbcggttciiippooaais', 2)

Expected Output: 'pis'

Input: ('', 2)

Expected Output: ''

Explanation: Empty input: nothing to remove.

Input: ('a', 2)

Expected Output: 'a'

Explanation: A single character cannot form a run of length >= 2.

Input: ('aaaa', 2)

Expected Output: ''

Explanation: One run of length 4 >= 2 is removed entirely, leaving the empty string.

Input: ('abcabc', 3)

Expected Output: 'abcabc'

Explanation: No two adjacent characters are equal, so no run reaches length 3; the string is unchanged.

Input: ('aabbaabb', 2)

Expected Output: ''

Explanation: Remove 'aa','bb','aa','bb' (all len 2). After they vanish there is nothing left; result is empty.

Input: ('abbabbbba', 2)

Expected Output: ''

Explanation: k=2 cascade: remove 'bb' -> 'aabbbba' wait/collapse merges; iterating removes every >=2 run until the whole string is consumed, yielding empty.

Input: ('cccacbaaaabbbbbca', 4)

Expected Output: 'cccacbca'

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'.

Last updated: Jun 26, 2026

Loading coding console...