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

What role is this question designed for?

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

Remove Repeated Character Groups | Attentive Coding Question

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.

Input: ("deeedbbcccbdaa", 3)

Expected Output: "aa"

Explanation: `eee` is removed, then the two `d` runs merge later through cascading deletions. After all possible removals, only `aa` remains.

Input: ("aaaa", 3)

Expected Output: ""

Explanation: The entire run `aaaa` has length 4, which is at least 3, so the whole string is removed.

Input: ("abccba", 2)

Expected Output: ""

Explanation: Remove `cc` -> `abba`, then remove `bb` -> `aa`, then remove `aa` -> empty string.

Input: ("baaab", 3)

Expected Output: "bb"

Explanation: Remove `aaa`, and the two remaining `b` characters become adjacent. Since their merged length is 2, which is less than 3, they stay.

Input: ("abc", 5)

Expected Output: "abc"

Explanation: No group has length at least 5, so nothing is removed.

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.

Quick Overview

This question evaluates proficiency in string manipulation, algorithmic thinking, and efficient use of data structures for handling contiguous character groups and iterative reductions.