The coding question
Given a string, remove any group of three or more of the same letter in a row, and keep doing it as new groups form. Return what's left.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| Does a group of four or more go all at once? | Yes. 'aaaa' disappears completely, not down to 'a'. |
| Is it case-sensitive? | Yes, 'a' and 'A' are different letters. |
| If two groups could go, which goes first? | The leftmost one. It matters in rare cases like 'abbbaaa', so ask. |
| What if nothing's left? | Return an empty string. |
A couple of examples
| Input | Output |
|---|---|
| 'aabbbacd' | 'cd': remove 'bbb', which makes 'aaa', then remove that |
| 'aabbccc' | 'aabb': only 'ccc' goes, and nothing new forms |
| 'abbbaaa' | '': remove 'bbb', which leaves 'aaaa', then that goes too |
| 'abcde' | 'abcde': nothing to remove |
Start with brute force
Scan the string for the first run of three or more, cut it out, and start over from the beginning. Stop when a full scan finds nothing.
Cost: each scan is O(n) and each removal takes out at least 3 letters, so up to n / 3 scans. That's O(n²).
A better way
When you remove a run, the only place a new run can form is right where it was, between the letters on its left and its right. Everything further left has already been checked. So you never need to go back and rescan.
That's what a stack is for. Push letters as you go, but store each run as one entry: the letter and how many in a row. When a different letter shows up, the run on top is finished. If it's 3 or more, pop it. Now the new top might be the same letter as the one arriving, so add to its count instead of pushing a new entry.
Wait until a run is finished before removing it, so 'aaaa' goes as one group. And check the top one more time at the end, since the last run never sees a different letter after it.
- Keep a stack of [letter, count] pairs.
- For each letter: if it matches the top, add 1 to the top's count and move on.
- Otherwise the top's run is done. If its count is 3 or more, pop it.
- Now if the letter matches the new top, add 1 to its count. If not, push [letter, 1].
- After the loop, pop the top if its count is 3 or more, then build the string from what's left.
The code
def crush(s):
stack = [] # [letter, how many in a row] for what's left so far
for ch in s:
if stack and stack[-1][0] == ch:
stack[-1][1] += 1
continue
# A different letter means the run on top is finished.
if stack and stack[-1][1] >= 3:
stack.pop()
# Popping can uncover a run of this same letter, so join it.
if stack and stack[-1][0] == ch:
stack[-1][1] += 1
else:
stack.append([ch, 1])
if stack and stack[-1][1] >= 3:
stack.pop()
return "".join(ch * count for ch, count in stack)| Cost | Why | |
|---|---|---|
| Time | O(n) | Each letter is added once, and each stack entry is popped at most once |
| Space | O(n) | The stack can hold up to n entries when nothing gets removed |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- Empty string: the loop never runs and it returns ''.
- Everything goes, like 'aaa' or 'abbbaaa': returns ''.
- A run at the very end, like 'aabbccc': the check after the loop catches it.
- Runs of exactly two, like 'aabb': they stay. Only 3 or more go.
- A removal that joins two pieces into a run, like 'aabbbaa': 'bbb' goes, then 'aa' and 'aa' join into 'aaaa', which goes when the string ends.
Common mistakes
- Popping as soon as a count hits 3. That breaks 'aaaa', leaving one 'a' behind.
- Pushing a new entry after a pop instead of joining the uncovered run, so 'aa' + 'a' never counts as 3.
- Forgetting the final check after the loop.
- Using a plain stack of single letters and counting back each time. It works, but it's slower and easy to get wrong.
Follow-up questions
What if groups of k or more go, not 3?
Change the 3 to k. Nothing else changes.
What if all groups that exist at once are removed together, not leftmost first?
Then 'abbbaaa' gives 'a', since 'bbb' and 'aaa' both go in the first round. Simulate it in rounds instead, marking every run in one pass, then removing them together.
How would you return how many letters were removed?
Add up the counts as you pop, or just return len(s) minus the length of the result.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Clarify runs of four, case and which group goes first |
| 5–10 | Brute force by rescanning, and why it's O(n²) |
| 10–20 | Why a removal only affects its neighbors, and the stack of counts |
| 20–35 | Write the code |
| 35–40 | Test 'aabbbacd', 'aabbccc' and 'abbbaaa' |
| 40–45 | Follow-up questions |
Key concepts used here
- Stacks and monotonic stacksMatch brackets, parse things, and find the next bigger value in one pass.
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Bloomberg.