Complexity Analysis:

• Time Complexity: $O(N^2)$. In the worst case (e.g., ((((...))))), we iterate through the string roughly $N/2$ times, and the string replacement operation takes $O(N)$ time.
• Space Complexity: $O(N)$ to store the modified string.

Why it fails: While correct logically, this approach is inefficient. Modifying strings repeatedly is costly. With constraints up to $10^4$ characters, an $O(N^2)$ solution performs roughly $10^8$ operations, which risks a Time Limit Exceeded (TLE) or performs very poorly compared to the optimal linear solution.

Core Insight for Valid Parentheses

The key intuition for the LeetCode 20 solution lies in the nature of nested structures. When we encounter an open bracket, we cannot validate it immediately; we must wait for its corresponding closing bracket. However, we know that the first closing bracket we encounter must match the last open bracket we saw.

If we encounter a closing bracket }, it is valid if and only if the most recent pending open bracket is {. If the most recent open bracket is ( or [, the nesting is invalid (e.g., (}).

Technical Visualization: Imagine the algorithm as a cursor moving left to right.

1. When the cursor hits an open bracket, it is pushed onto a stack. This represents a "pending" expectation.
2. When the cursor hits a closing bracket, we peek at the top of the stack.
3. If the stack is empty, we have a closing bracket with no previous opener (Invalid).
4. If the top matches the current closer, we pop the stack (expectation fulfilled).
5. If the top does not match, the types are mismatched (Invalid).

At the end of the string, a valid input results in an empty stack, meaning all expectations were fulfilled.

Execution Flow

Let's trace the algorithm with the input s = "([{}])".

1. Start: Stack is empty [].
2. Process (: It is an open bracket. Push to stack.
   • Stack: ['(']
3. Process [: It is an open bracket. Push to stack.
   • Stack: ['(', '[']
4. Process {: It is an open bracket. Push to stack.
   • Stack: ['(', '[', '{']
5. Process }: It is a closing bracket.
   • Check top of stack: {.
   • Does } match {? Yes.
   • Pop stack.
   • Stack: ['(', '[']
6. Process ]: It is a closing bracket.
   • Check top of stack: [.
   • Does ] match [? Yes.
   • Pop stack.
   • Stack: ['(']
7. Process ): It is a closing bracket.
   • Check top of stack: (.
   • Does ) match (? Yes.
   • Pop stack.
   • Stack: [] (Empty)
8. End: The string is finished. Is stack empty? Yes. Return true.

Proof of Correctness

The algorithm is correct based on the invariant of the stack:

1. LIFO Property: The stack always exposes the most recently seen open bracket. By the definition of valid parentheses, this is the only bracket that can validly be closed next.
2. Type Safety: We explicitly check that the closing bracket type matches the open bracket type at the top of the stack.
3. Balance Check:
   • If we have too many closing brackets, the stack underflows (empty check).
   • If we have too many open brackets, the stack is non-empty at the end.
   • Therefore, returning true only when the stack is empty ensures a 1:1 mapping.

Reference Implementation

C++ Solution for LeetCode 20

cpp
#include <stack>
#include <string>
#include <unordered_map>

class Solution {
public:
    bool isValid(std::string s) {
        std::stack<char> st;
        
        for (char c : s) {
            // If it's an open bracket, push to stack
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            } else {
                // If stack is empty, we have a closing bracket without an opener
                if (st.empty()) return false;
                
                char top = st.top();
                // Check for mismatch
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
                // Valid match found, pop the open bracket
                st.pop();
            }
        }
        
        // Stack must be empty for valid string
        return st.empty();
    }
};

Java Solution for LeetCode 20

java
import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s) {
            // If open bracket, push onto stack
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                // If stack is empty, unbalanced closing bracket
                if (stack.isEmpty()) {
                    return false;
                }
                
                char top = stack.pop();
                
                // Check for matching pair
                if (c == ')' && top != '(') return false;
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
            }
        }
        
        // If stack is not empty, we have unmatched open brackets
        return stack.isEmpty();
    }
}

Python Solution for LeetCode 20

python
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        # Map closing brackets to their corresponding open brackets
        mapping = {")": "(", "}": "{", "]": "["}
        
        for char in s:
            if char in mapping:
                # It is a closing bracket
                # Pop the top element if stack is not empty, else assign dummy value
                top_element = stack.pop() if stack else '#'
                
                # If the mapped open bracket doesn't match the popped element, return False
                if mapping[char] != top_element:
                    return False
            else:
                # It is an open bracket
                stack.append(char)
        
        # If the stack is empty, return True
        return not stack