Problem: Valid Parentheses

Problem Statement

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.

Approach: Stack-Based Validation

A stack is the perfect data structure here because it follows Last-In, First-Out (LIFO). The last opening bracket seen must be the first one to be closed.

1. Iterate: Loop through each character in the string.
2. Opening Brackets: If we see (, {, or [, push the corresponding closing bracket onto the stack.
3. Closing Brackets: If we see a closing bracket:
   • If the stack is empty, it's invalid (no matching opening bracket).
   • Pop from the stack. If the popped value doesn't match the current character, it's invalid.
4. Final Check: After the loop, the stack must be empty.

Java Implementation

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '{') stack.push('}');
        else if (c == '[') stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

Complexity Analysis

• Time Complexity: $O(n)$. We visit every character once.
• Space Complexity: $O(n)$. In the worst case (all opening brackets), the stack size equals the string length.

Interview Tips

• Why use a stack? "Because brackets are nested, and we need to match the most recent opener with the current closer."
• Handle edge cases: Single character strings, empty strings.