Crack the Backend

Problem Statement

Given a string s containing only the characters (, ), {, }, [, ], determine if the input string is valid. Valid means: every opening bracket has a closing bracket of the same type and brackets are closed in the correct order (e.g. "([)]" is invalid).

An empty string is valid. We need to match each closing bracket with the most recent unmatched opening bracket of the same type — a stack is the right structure.

Key Observations

When we see an opening bracket (, {, [, we push it onto the stack. When we see a closing bracket, the stack must not be empty and the top must be the matching opening; we pop. If at any step the stack is empty when we see a closing bracket, or the top does not match, return false. At the end, the stack must be empty (all opened brackets were closed).
Use a map from closing to opening for easy matching: ')' -> '(', etc.

Approach

High-level: Stack. For each character: if it's opening, push. If it's closing: if stack is empty or pop() != matching opening, return false. After the loop, return stack.isEmpty().

Steps:

Map<Character, Character> map closing → opening. Deque<Character> stack. For each char: if map.containsKey(char) (closing), if stack.isEmpty() or stack.pop() != map.get(char) return false; else stack.push(char).
Return stack.isEmpty().

Implementation

Java

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') stack.push(c);
            else {
                if (stack.isEmpty() || stack.pop() != map.get(c)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

Test Cases

Example 1

Input

s = "()"

Expected

true

Explanation

Valid.

Complexity Analysis

Time: O(n).
Space: O(n).

Follow-ups

Generate all valid combinations of n pairs of parentheses.