☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Balanced Paranthesis

Easy TUF ID 966 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string s made only of the six bracket characters (, ), [, ], {, }. Decide whether it is balanced: every opening bracket is closed by a bracket of the same kind, brackets close in the reverse order they were opened, and no closing bracket appears without a matching opener. An empty string is balanced.

Constraints: 0 ≤ n ≤ 10^4.

Example 1

s = "{[()]}"
answer = true            // each closer matches the most recent unclosed opener

Example 2

s = "([)]"
answer = false           // ')' arrives while '[' is the most recent unclosed opener

Example 3

s = "(()"
answer = false           // one '(' is never closed

Approach 1: Brute force, cancel adjacent pairs

Intuition. In a balanced string there is always at least one pair of brackets that are adjacent and match, such as the () in the middle of {[()]}: the innermost pair has nothing between its two halves. Deleting such a pair leaves a shorter string that is still balanced, and repeating the deletion eventually leaves nothing. Conversely, if the string is unbalanced, at some point no adjacent matching pair exists and something is left over. So: strip (), [] and {} repeatedly and check whether the string vanishes.

Algorithm.

  1. Repeat: replace every occurrence of (), [], {} in the string with the empty string.
  2. Stop when a round removes nothing (the length did not change).
  3. Return true if the remaining string is empty.
static boolean bruteForce(String s) {
    String cur = s;
    while (true) {
        String next = cur.replace("()", "").replace("[]", "").replace("{}", "");
        if (next.length() == cur.length()) break;      // no adjacent pair left to remove
        cur = next;
    }
    return cur.isEmpty();
}

Complexity. Time O(n^2): each round scans the whole string in O(n), and since every productive round removes at least two characters there are at most n/2 rounds. A deeply nested string such as ((((...)))) really does need n/2 rounds. Space O(n) for the intermediate strings.

This is a fine way to explain balance, and it is easy to get right, but it is quadratic and allocates a new string per round. The stack approach does one pass.

Approach 2: Optimal, a stack of open brackets

Intuition. Read left to right. An opening bracket creates an obligation: “something must close me later”. The obligation created most recently is the one that must be met first, which is exactly last-in-first-out behaviour. So push openers on a stack. When a closer arrives, the top of the stack is the only bracket it is allowed to close: if the stack is empty, or the top is a different kind, the string is invalid. At the end, any opener still on the stack was never closed.

Algorithm.

  1. Create an empty stack of characters.
  2. For each character c of s:
    • If c is (, [ or {, push it.
    • Otherwise c is a closer. If the stack is empty, return false. Pop the top; if it is not the opener matching c, return false.
  3. Return true if the stack is empty, false otherwise.
static boolean optimal(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;         // a closer with nothing open
            char open = stack.pop();
            if (!matches(open, c)) return false;       // the wrong kind of closer
        }
    }
    return stack.isEmpty();                            // anything still open was never closed
}

static boolean matches(char open, char close) {
    return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}');
}

Dry run on example 2, s = "([)]":

i c stack before action
0 ( [] push → [(]
1 [ [(] push → [(, []
2 ) [(, [] pop [, does not match ) → return false

And on example 1, s = "{[()]}": push {, push [, push (, then ) pops (, ] pops [, } pops {, stack empty → true.

Complexity. Time O(n): each character is pushed and popped at most once. Space O(n) for the stack in the worst case, for example (((( followed by )))).

Approach 3: Push the expected closer

Intuition. The matches table exists because we store what we saw and later compare it with what we see. If instead we push what we expect to see, the comparison becomes a plain equality: on ( push ), on [ push ], on { push }. A closer is then valid exactly when it equals the top of the stack. The logic is the same as approach 2, only the bookkeeping is simpler, and it extends to any number of bracket kinds without a growing matches method.

A cheap early exit comes for free: brackets pair up, so an odd-length string can never be balanced.

Algorithm.

  1. If s.length() is odd, return false.
  2. For each character: if it is an opener, push its partner closer. Otherwise, if the stack is empty or its top differs from the character, return false; else pop.
  3. Return whether the stack is empty.
static boolean optimalExpectedCloser(String s) {
    if (s.length() % 2 != 0) return false;             // an odd number of brackets can never pair up
    Deque<Character> expected = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(' -> expected.push(')');
            case '[' -> expected.push(']');
            case '{' -> expected.push('}');
            default -> {
                if (expected.isEmpty() || expected.pop() != c) return false;
            }
        }
    }
    return expected.isEmpty();
}

Complexity. Time O(n), space O(n), as in approach 2, with one fewer method call per closer.

Edge cases and pitfalls