Balanced Parenthesis problem

The problem, simply

You get a string made of brackets: round ( ), square [ ] and curly { }. Say if it is balanced.

Balanced means two things. Every opener has a closer of the same kind. And they close in the right order: whatever opened last must close first. So {[()]} is fine, but ([)] is not, because the [ opened after the ( and must close before it.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look for a pair that is right next to each other, like (), [] or {}, and erase it. Erasing it may make a new pair touch, so keep going. If the string becomes empty, it was balanced.

1. Find any (), [] or {} in the string.
2. Remove it.
3. Repeat until no such pair is left.
4. Balanced if and only if nothing is left.

class Solution {
    public boolean isBalanced(String s) {
        String prev;
        do {
            prev = s;
            // rub out every pair that is touching
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (!s.equals(prev));   // stop when nothing changed
        return s.isEmpty();
    }
}

How long it takes: each pass walks the whole string, and a deep string like ((((...)))) loses only one pair per pass, so up to n / 2 passes. That is O(n^2). Extra room: each pass builds a new string, O(n).

Way 2: the clever way

Use the cup of tokens from the story. In code the cup is a stack: a pile where you only touch the top.

1. Read the brackets from left to right.
2. An opener goes into the cup.
3. A closer must match the top of the cup. If the cup is empty, or the top is a different kind, answer false. If it matches, take the top out.
4. When the string ends, the cup must be empty. Anything left over never got closed.

Now the crossed string ([)]. Counting says two of each, but the cup catches the problem:

import java.util.*;

class Solution {
    public boolean isBalanced(String s) {
        Deque<Character> cup = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                cup.push(c);                         // opener waits in the cup
            } else {
                if (cup.isEmpty()) return false;     // nobody to close
                char top = cup.pop();
                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }
        return cup.isEmpty();                        // leftovers mean false
    }
}

How long it takes: each bracket goes into the cup at most once and comes out at most once, O(n). Extra room: the cup can hold every bracket when they are all openers, O(n).

Another way: only one kind of bracket

If the string has only ( and ), the cup only ever holds (, so you can replace it with a counter. Add 1 for (, take 1 for ). The counter must never go below zero, and it must end at zero.

class Solution {
    public boolean isBalanced(String s) {
        int open = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (c == ')') {
                open--;
                if (open < 0) return false;   // a closer came too early
            }
        }
        return open == 0;
    }
}

This is O(n) time and O(1) room. It does not work for three kinds: ([)] keeps every counter happy but is wrong. The order between kinds needs the stack.

Watch out for

• Popping from an empty stack. Check for empty before you pop, or )( will crash.
• Using three separate counters for three kinds. That misses crossed pairs like ([)].
• Odd length strings can never be balanced. You can return false at once as a small speed up.
• Java's old Stack class works, but ArrayDeque is the modern choice and is faster.

What interviewers ask next

• Fewest brackets to add to make ( and ) balanced? Keep the counter. When it would go below zero, count one needed ( and stay at zero. At the end add whatever is still open.
• Longest balanced piece inside a string? Push indexes instead of brackets, with -1 at the bottom as a fence. After each pop, the distance to the new top is a balanced length.
• Print every balanced string with n pairs? Backtracking: add ( while you have some left, add ) only while it would not close more than you opened.
• Fewest flips to fix a string of ( and )? Cancel every matched pair first. You are left with a closers then b openers, like )))(((. The answer is ceil(a / 2) + ceil(b / 2), and it is impossible when the length is odd.
• What if other characters are mixed in, like code a[i] = (b + c);? Skip anything that is not a bracket. The same cup works.

Remember this

Grown-up words: the cup of tokens is a stack, "last in, first out" is LIFO order, the doors closing in reverse is proper nesting, and the counter trick works only because one kind of bracket needs no memory of which kind is open.