Recursively remove all adjacent duplicates

The problem, simply

You get a word. Look for a block of two or more of the same letter standing side by side, like xx or xxx. Remove the whole block. The letters on its left and right now stand next to each other, and they may form a new block. Keep removing until no letter has an identical neighbor.

Give back what is left. It may be an empty string.

Order can matter, so we use one fixed rule: always remove the leftmost block first. This is what a left to right scan does, and it gives the answers the classic problem expects.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do exactly what the rule says, over and over.

1. Scan from the left until you find a letter that equals the next one.
2. Stretch to the right to cover the whole block of that letter.
3. Cut the block out and glue the two sides together.
4. Start scanning from the beginning again. Stop when a full scan finds no block.

class Solution {
    public String removeDuplicates(String s) {
        while (true) {
            int i = 0;
            // find the first letter that has a twin on its right
            while (i + 1 < s.length() && s.charAt(i) != s.charAt(i + 1)) i++;
            if (i + 1 >= s.length()) return s;          // no block left
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;  // whole block
            s = s.substring(0, i) + s.substring(j);    // cut it out, glue the sides
        }
    }
}

How long it takes: each cut can make us rescan and copy the whole word, and there can be about n / 2 cuts, so O(n^2). Extra room: the new copy of the word, O(n).

Way 2: the clever way

Keep the letters you have already checked in a pile, a stack, with the last one on top. Store each entry as a letter and how many times it is repeated right now.

1. A new letter that equals the top letter makes the top block one bigger.
2. A new letter that is different first looks at the top block. If that block has two or more letters, it is finished, so it pops off the pile.
3. After a pop, the new top may equal the new letter. Then they are twins that just rolled together, so the top block grows to two.
4. Otherwise put the new letter on top with a count of one.
5. At the end, pop the top block if it has two or more letters. What is left on the pile, bottom to top, is the answer.

Only the top block can ever have a count bigger than one, so each step looks at one or two entries at most.

class Solution {
    public String removeDuplicates(String s) {
        int n = s.length();
        char[] letter = new char[n];   // the pile: letter of each block
        int[] count = new int[n];      // the pile: size of each block
        int top = -1;                  // top of the pile, -1 means empty

        for (int k = 0; k < n; k++) {
            char c = s.charAt(k);
            if (top >= 0 && letter[top] == c) {    // same as top: block grows
                count[top]++;
                continue;
            }
            if (top >= 0 && count[top] > 1) top--; // finished block of twins pops
            if (top >= 0 && letter[top] == c) {    // sides rolled together and match
                count[top]++;
                continue;
            }
            top++;                                 // a fresh block of one letter
            letter[top] = c;
            count[top] = 1;
        }
        if (top >= 0 && count[top] > 1) top--;     // the last block may be twins too

        StringBuilder out = new StringBuilder();
        for (int k = 0; k <= top; k++) out.append(letter[k]);
        return out.toString();
    }
}

How long it takes: every letter is pushed or added to a block once and popped at most once, O(n). Extra room: the pile can hold every letter, O(n).

Watch out for

• The last block. When the loop ends, the top block may still be a group of twins, as in abb. Pop it after the loop.
• Removing every block in one sweep is a different rule. On abbaa the one sweep rule removes bb and aa together and leaves a. The leftmost first rule removes bb, then the three a letters meet and pop, leaving the empty string. Ask which rule the interviewer means.
• Building the answer with s = s + c inside a loop copies the word each time. Use a StringBuilder.
• The answer can be empty. Return "", not null.

What interviewers ask next

• Only remove pairs (LeetCode 1047). Use a plain stack of letters: if the new letter equals the top, pop, otherwise push.
• Remove blocks of exactly k equal letters (LeetCode 1209). Keep a count on each stack entry and pop when the count reaches k.
• Can you do it without an extra stack? Yes. Use the answer StringBuilder itself as the pile and keep the counts in an int[], which still costs O(n) but no extra objects.
• Why is the stack answer the same as removing the leftmost block again and again? Everything left of the top is already free of twins, so the top block is always the leftmost block that can pop next.

Remember this

Grown-up words: the glass of bubbles is a stack, a block of the same letter is a run, the pop then match step is merging runs after deletion, and the one pass is linear time.