Collapse Adjacent Duplicate Letters
Solve this Problems, repeatedly remove any two adjacentAdjacentDirectly next to each other in the current string — after a removal, characters that weren't originally adjacent can become adjacent, potentially triggering another removal. identical characters until no such pair remains, and return the final result.
Because a removal can expose a brand-new adjacent match — collapsing "mississippi" strips the double 's', which brings the double 'i' together — the naive approach has to keep re-scanning from the top until a full pass changes nothing. A single-pass stack sidesteps the re-scanning entirely: compare each new character only to whatever is currently on top of the stack. A match means that pair just cancelled, so pop instead of pushing — which conveniently exposes exactly the right character to compare against next, letting cascades resolve for free within one linear pass.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 20 - ◆
s consists only of lowercase English letters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeatedly Remove Adjacent Duplicate Pairs
BruteScan the string for any two adjacent identical characters and remove that pair, shrinking the string. Removing one pair can bring previously non-adjacent characters together (as in "mississippi", where collapsing the 's's exposes the 'i's right next to each other), so repeat the scan from the top until a full pass finds nothing left to remove. Each pass is O(n), and up to n/2 passes may cascade, so this costs O(n²) overall.
O(n²)O(n)1class Solution {
2 public String collapseAdjacentDuplicates(String s) {
3 boolean changed = true;
4 while (changed) {
5 changed = false;
6 for (int i = 0; i < s.length() - 1; i++) {
7 if (s.charAt(i) == s.charAt(i + 1)) {
8 s = s.substring(0, i) + s.substring(i + 2);
9 changed = true;
10 break;
11 }
12 }
13 }
14 return s;
15 }
16}Optimal — Single Pass With a Character Stack
OptimalWalk the string once, keeping a stack of characters that have survived so far. For each new character, compare it to the stack's top: if they match, pop (the pair just cancelled out — exactly like the brute-force removal, but discovered immediately instead of via re-scanning); otherwise, push the new character. Whatever remains on the stack at the end, read bottom to top, is the final collapsed string — cascading cancellations (like in "mississippi") fall out naturally, since a pop can expose a new top that matches the very next character.
O(n)O(n)1class Solution {
2 public String collapseAdjacentDuplicates(String s) {
3 StringBuilder stack = new StringBuilder();
4 for (char c : s.toCharArray()) {
5 if (stack.length() > 0 && stack.charAt(stack.length() - 1) == c) {
6 stack.deleteCharAt(stack.length() - 1);
7 } else {
8 stack.append(c);
9 }
10 }
11 return stack.toString();
12 }
13}