Valid Parentheses

Concept

LeetCode #20.
Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Input: s = "()[]{}" -> Output: true
Input: s = "(]" -> Output: false
Input: s = "([)]" -> Output: false (Wrong order! The [ must be closed before the ( can be closed).

The Stack Strategy

This is the quintessential Stack problem.
A Stack operates on LIFO (Last In, First Out) principles.

When you see an Opening Bracket ((, {, [), you are opening a new context. You push it onto the Stack.
When you see a Closing Bracket (), }, ]), it MUST perfectly match the most recently opened context! Where is the most recently opened context? It’s sitting exactly at the absolute Top of the Stack!

1. Loop through the string.
2. If it’s an Opening Bracket: Push it onto the Stack.
3. If it’s a Closing Bracket:
   • Pop the absolute top element off the Stack.
   • Does this popped element perfectly match the Closing Bracket?
   • If YES: Great, that pair is closed. Continue!
   • If NO: The string is completely invalid. Return false.
4. At the very end of the string, the Stack MUST be perfectly empty. If there is anything left on the Stack, it means there is an unclosed Opening Bracket. Return false.

Implementation

We use a Hash Map to perfectly map the closing brackets to their required opening brackets. This completely eliminates the need for massive if/else or switch statements!

// Time Complexity: O(N) (One pass through the string)
// Space Complexity: O(N) (In the worst case, the stack holds every character "(((((")

function isValid(s: string): boolean {
    // Optimization: An odd-length string is mathematically impossible to be valid
    if (s.length % 2 !== 0) return false;

    // The Map perfectly pairs the brackets!
    const bracketMap = new Map<string, string>([
        [')', '('],
        ['}', '{'],
        [']', '[']
    ]);

    const stack: string[] = [];

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        // Is it a Closing Bracket? (Is it a Key in our Map?)
        if (bracketMap.has(char)) {
            
            // Pop the top of the stack! (If stack is empty, .pop() returns undefined)
            const topElement = stack.pop();

            // Does the top element match what the Map says it SHOULD be?
            if (topElement !== bracketMap.get(char)) {
                return false; // Mismatch! Invalid string.
            }

        } else {
            // It's an Opening Bracket! Push it onto the Stack.
            stack.push(char);
        }
    }

    // If the stack is perfectly empty at the end, we successfully closed everything!
    return stack.length === 0;
}

The “Inverted Push” Trick

There is a brilliant, slightly faster alternative implementation.
Instead of pushing the Opening Bracket onto the stack and using a Map to check it… when you see an Opening Bracket, you push the Expected Closing Bracket onto the stack!

If you see (, you physically push ) onto the stack.
Later, when you actually encounter a Closing Bracket in the string, you just pop the stack and check if char === poppedElement! This completely removes the need for a Hash Map!

function isValidInverted(s: string): boolean {
    const stack: string[] = [];

    for (const char of s) {
        if (char === '(') stack.push(')');
        else if (char === '{') stack.push('}');
        else if (char === '[') stack.push(']');
        else {
            // It's a closing bracket! Just pop and match!
            if (stack.length === 0 || stack.pop() !== char) {
                return false;
            }
        }
    }

    return stack.length === 0;
}

Interview Questions

Q: A developer suggests using Regular Expressions to repeatedly s = s.replace("()", "").replace("[]", "") in a while loop until the string is empty. Is this viable?
A: This is a horrible anti-pattern. While functionally correct, string .replace() allocates an entirely new string in memory every single time it runs. If you have a massive string of 10,000 brackets (((((...))))), this loop will execute 5,000 times, creating 5,000 massive strings in RAM, utterly destroying the Garbage Collector and degrading the time complexity to $O(N^2)$. The Stack is $O(N)$ and mutates a single array in place.