Parentheses and Bracket Patterns

1. Valid Parentheses Using Stack

Approach	Method	Time	Space
Stack Matching	Push opening brackets, pop and match closing	`O(n)`	`O(n)`
Counter Optimization	For single type, use counter instead of stack	`O(n)`	`O(1)`
HashMap Lookup	Map closing to opening for quick validation	`O(n)`	Cleaner code
Replace Pattern	Repeatedly remove valid pairs (inefficient)	`O(n^2)`	Not recommended

Example: Stack-based validation

function isValid(s) {
    const stack = [];
    const pairs = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (const char of s) {
        if (char === '(' || char === '{' || char === '[') {
            // Opening bracket - push to stack
            stack.push(char);
        } else {
            // Closing bracket - check match
            if (stack.length === 0) {
                return false; // No opening bracket
            }
            
            const top = stack.pop();
            if (top !== pairs[char]) {
                return false; // Mismatch
            }
        }
    }
    
    // Valid if stack is empty (all matched)
    return stack.length === 0;
}

// Example: "({})"
// '(' -> push
// '{' -> push
// '}' -> pop '{', match ✓
// ')' -> pop '(', match ✓
// Stack empty -> valid

// Example: "([)]"
// '(' -> push
// '[' -> push
// ')' -> pop '[', mismatch ✗

Example: Cleaner with early returns

function isValidCleaner(s) {
    const stack = [];
    const map = new Map([
        [')', '('],
        ['}', '{'],
        [']', '[']
    ]);
    
    for (const char of s) {
        if (map.has(char)) {
            // Closing bracket
            const top = stack.pop();
            if (top !== map.get(char)) {
                return false;
            }
        } else {
            // Opening bracket
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

// Key insights:
// 1. Stack stores opening brackets only
// 2. Closing bracket triggers pop and validation
// 3. Empty stack at end means all matched
// 4. Early return on mismatch or empty stack

Example: Optimized for single bracket type

// For strings with only one type of bracket: ()
function isValidSingleType(s) {
    let count = 0;
    
    for (const char of s) {
        if (char === '(') {
            count++;
        } else if (char === ')') {
            count--;
            if (count < 0) {
                return false; // More closing than opening
            }
        }
    }
    
    return count === 0;
}

// O(1) space vs O(n) for stack
// Can't handle multiple bracket types
// Useful for specific problems like balanced parentheses count

2. Generate Parentheses (Backtracking)

Approach	Strategy	Time	Space
Backtracking	Add '(' or ')' based on constraints	`O(4^n / √n)` Catalan	`O(n)` depth
Constraint: Open	Can add '(' if open < n	Ensures not too many	Critical rule
Constraint: Close	Can add ')' if close < open	Ensures valid matching	Critical rule
Closure Number	DP approach using Catalan recurrence	`O(4^n / √n)`	Alternative method

Example: Backtracking generation

function generateParenthesis(n) {
    const result = [];
    
    function backtrack(current, open, close) {
        // Base case: generated n pairs
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        
        // Can add opening bracket if haven't used n yet
        if (open < n) {
            backtrack(current + '(', open + 1, close);
        }
        
        // Can add closing bracket if it matches an opening
        if (close < open) {
            backtrack(current + ')', open, close + 1);
        }
    }
    
    backtrack('', 0, 0);
    return result;
}

// Example: n=3
// Result: ["((()))","(()())","(())()","()(())","()()()"]

// Decision tree for n=2:
//                    ""
//              (0,0)
//               /
//             "("
//           (1,0)
//          /     \
//       "(("    "()"
//      (2,0)   (1,1)
//        |       |
//     "(()"    "()(
//     (2,1)    (2,1)
//       |        |
//    "(())"   "()()"
//    (2,2)    (2,2)

Example: Alternative with explicit tracking

function generateParenthesisExplicit(n) {
    const result = [];
    
    function generate(current, open, close, max) {
        if (current.length === max * 2) {
            result.push(current);
            return;
        }
        
        // Always try adding '(' first (if possible)
        if (open < max) {
            generate(current + '(', open + 1, close, max);
        }
        
        // Then try adding ')' (if valid)
        if (close < open) {
            generate(current + ')', open, close + 1, max);
        }
    }
    
    generate('', 0, 0, n);
    return result;
}

// Key constraints visualized:
// - open < n: haven't exhausted opening brackets
// - close < open: have unmatched opening brackets
// Both must be true to maintain validity

Note: The number of valid parentheses combinations for n pairs is the nth Catalan number: $C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$. For n=3, this is 5 combinations. The time complexity is proportional to the number of valid combinations.

3. Longest Valid Parentheses (DP Solution)

Approach	Method	Time	Space
Dynamic Programming	dp[i] = length ending at index i	`O(n)`	`O(n)`
Stack Indices	Track indices of unmatched brackets	`O(n)`	`O(n)`
Two Pass Counter	Left-to-right then right-to-left	`O(n)`	`O(1)`
Brute Force	Check all substrings	`O(n^3)`	Not practical

Example: DP approach

function longestValidParentheses(s) {
    const n = s.length;
    const dp = new Array(n).fill(0);
    let maxLen = 0;
    
    for (let i = 1; i < n; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                // Case 1: ...()
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && 
                       s[i - dp[i - 1] - 1] === '(') {
                // Case 2: ...))
                // dp[i-1] is length of valid substring ending at i-1
                // Check if char before that substring is '('
                dp[i] = dp[i - 1] + 2;
                
                // Add length before matching '(' if exists
                const beforeMatch = i - dp[i - 1] - 2;
                if (beforeMatch >= 0) {
                    dp[i] += dp[beforeMatch];
                }
            }
            
            maxLen = Math.max(maxLen, dp[i]);
        }
    }
    
    return maxLen;
}

// Example: s = "()(()"
// Index:  0 1 2 3 4
// Char:   ( ) ( ( )
// dp:     0 2 0 0 2
// 
// i=1: s[1]=')' and s[0]='(' -> dp[1] = 0 + 2 = 2
// i=4: s[4]=')' and s[3]='(' -> dp[4] = 0 + 2 = 2
// Max: 2

// Example: s = "()(())"
// Index:  0 1 2 3 4 5
// Char:   ( ) ( ( ) )
// dp:     0 2 0 0 2 6
// 
// i=1: '()' -> dp[1] = 2
// i=4: '()' inside -> dp[4] = 2
// i=5: '))' -> dp[5] = dp[4] + 2 + dp[1] = 2 + 2 + 2 = 6
// Max: 6

Example: Stack approach

function longestValidParenthesesStack(s) {
    const stack = [-1]; // Base for valid substring
    let maxLen = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            
            if (stack.length === 0) {
                // No matching '(' - new base
                stack.push(i);
            } else {
                // Valid substring from stack.top to i
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    
    return maxLen;
}

// Example: s = "(()"
// i=0, '(': stack = [-1, 0]
// i=1, '(': stack = [-1, 0, 1]
// i=2, ')': pop 1, length = 2 - 0 = 2, stack = [-1, 0]
// Max: 2

// Stack stores indices of unmatched brackets
// Length = current index - index before unmatched portion

Example: Two-pass O(1) space

function longestValidParenthesesConstant(s) {
    let left = 0, right = 0, maxLen = 0;
    
    // Left to right pass
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            left++;
        } else {
            right++;
        }
        
        if (left === right) {
            maxLen = Math.max(maxLen, 2 * right);
        } else if (right > left) {
            left = right = 0; // Reset
        }
    }
    
    left = right = 0;
    
    // Right to left pass
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === '(') {
            left++;
        } else {
            right++;
        }
        
        if (left === right) {
            maxLen = Math.max(maxLen, 2 * left);
        } else if (left > right) {
            left = right = 0; // Reset
        }
    }
    
    return maxLen;
}

// Two passes handle cases where extra brackets are on different sides
// Left-to-right: handles extra '(' at end
// Right-to-left: handles extra '(' at start
// O(1) space, O(n) time

4. Remove Invalid Parentheses (BFS)

Approach	Method	Time	Space
BFS Level-by-level	Remove one char at a time, check validity	`O(2^n)`	`O(2^n)`
Backtracking	Count invalid brackets, try removing	`O(2^n)`	`O(n)` depth
Early Termination	Stop when first valid strings found	BFS guarantees minimum removals	Key optimization
Deduplication	Use Set to avoid duplicate processing	Critical for performance	Prevents exponential blowup

Example: BFS with early termination

function removeInvalidParentheses(s) {
    const result = [];
    const visited = new Set();
    const queue = [s];
    visited.add(s);
    let found = false;
    
    function isValid(str) {
        let count = 0;
        for (const char of str) {
            if (char === '(') count++;
            else if (char === ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count === 0;
    }
    
    while (queue.length > 0) {
        const current = queue.shift();
        
        if (isValid(current)) {
            result.push(current);
            found = true;
        }
        
        if (found) continue; // Don't generate more levels
        
        // Generate all possible states by removing one bracket
        for (let i = 0; i < current.length; i++) {
            // Only remove parentheses
            if (current[i] !== '(' && current[i] !== ')') {
                continue;
            }
            
            const next = current.slice(0, i) + current.slice(i + 1);
            
            if (!visited.has(next)) {
                visited.add(next);
                queue.push(next);
            }
        }
    }
    
    return result.length > 0 ? result : [''];
}

// Example: s = "()())()"
// Level 0: "()())()" (invalid)
// Level 1: Remove one bracket, check each
// First valid found at minimal removal
// Result: ["(())()","()()()"]

// BFS ensures minimum removals by checking level-by-level

Example: Backtracking with counting

function removeInvalidParenthesesBacktrack(s) {
    const result = [];
    
    // Count invalid brackets
    let leftRemove = 0, rightRemove = 0;
    for (const char of s) {
        if (char === '(') {
            leftRemove++;
        } else if (char === ')') {
            if (leftRemove > 0) {
                leftRemove--;
            } else {
                rightRemove++;
            }
        }
    }
    
    function backtrack(index, leftRem, rightRem, 
                       leftCount, rightCount, current) {
        if (index === s.length) {
            if (leftRem === 0 && rightRem === 0) {
                result.push(current);
            }
            return;
        }
        
        const char = s[index];
        
        // Option 1: Remove this bracket
        if ((char === '(' && leftRem > 0) || 
            (char === ')' && rightRem > 0)) {
            backtrack(
                index + 1,
                leftRem - (char === '(' ? 1 : 0),
                rightRem - (char === ')' ? 1 : 0),
                leftCount,
                rightCount,
                current
            );
        }
        
        // Option 2: Keep this character
        if (char !== '(' && char !== ')') {
            // Regular character - always keep
            backtrack(index + 1, leftRem, rightRem, 
                     leftCount, rightCount, current + char);
        } else if (char === '(') {
            // Keep opening bracket
            backtrack(index + 1, leftRem, rightRem, 
                     leftCount + 1, rightCount, current + char);
        } else if (rightCount < leftCount) {
            // Keep closing bracket if valid
            backtrack(index + 1, leftRem, rightRem, 
                     leftCount, rightCount + 1, current + char);
        }
    }
    
    backtrack(0, leftRemove, rightRemove, 0, 0, '');
    return [...new Set(result)]; // Deduplicate
}

// Pre-compute how many brackets need removal
// Backtrack with constraints to generate only valid removals

5. Minimum Add to Make Valid Parentheses

Approach	Method	Time	Space
Counter Method	Track unmatched opening and closing	`O(n)`	`O(1)`
Stack Count	Use stack size + extra counter	`O(n)`	`O(n)`
Balance Tracking	Maintain running balance, count negatives	`O(n)`	`O(1)`
Two Variables	open (unmatched '('), close (unmatched ')')	Simplest approach	Recommended

Example: Counter approach

function minAddToMakeValid(s) {
    let open = 0;   // Unmatched '('
    let close = 0;  // Unmatched ')'
    
    for (const char of s) {
        if (char === '(') {
            open++;
        } else {
            if (open > 0) {
                open--; // Match with previous '('
            } else {
                close++; // No '(' to match
            }
        }
    }
    
    // open: need ')' to close
    // close: need '(' to open
    return open + close;
}

// Example: s = "())"
// '(' -> open=1
// ')' -> open=0 (matched)
// ')' -> close=1 (unmatched)
// Result: 0 + 1 = 1 (need one '(')

// Example: s = "((("
// open=3 at end
// Result: 3 (need three ')')

Example: Balance tracking

function minAddToMakeValidBalance(s) {
    let balance = 0;
    let additions = 0;
    
    for (const char of s) {
        if (char === '(') {
            balance++;
        } else {
            balance--;
        }
        
        // If balance goes negative, need '(' before
        if (balance < 0) {
            additions++;
            balance = 0; // Reset after adding '('
        }
    }
    
    // balance = unmatched '(' at end
    return additions + balance;
}

// Example: s = "))(("
// ')' -> balance=-1 -> additions=1, reset
// ')' -> balance=-1 -> additions=2, reset
// '(' -> balance=1
// '(' -> balance=2
// Result: 2 + 2 = 4

// additions: '(' needed before
// balance: ')' needed after

// Related: Minimum number of swaps to make valid
// Only '(' and ')' with equal count
function minSwapsToMakeValid(s) {
    let open = 0;
    let unbalanced = 0;
    
    for (const char of s) {
        if (char === '(') {
            open++;
        } else {
            if (open > 0) {
                open--;
            } else {
                unbalanced++;
            }
        }
    }
    
    // Number of swaps = ceil(unbalanced / 2)
    return Math.ceil(unbalanced / 2);
}

// Example: s = "))(("
// unbalanced = 2 (two ')' before any '(')
// Swaps needed: ceil(2/2) = 1
// Swap positions 0 and 2: "()()"

// Each swap fixes two unbalanced brackets

Summary: Parentheses Problems Patterns

Valid Parentheses: Stack of opening brackets, pop and match on closing, valid if stack empty at end - O(n) time, O(n) space
Stack Pattern: Push '(' '{' '[', on ')' '}' ']' pop and verify match, HashMap maps closing to opening for quick lookup
Single Type Optimization: Use counter instead of stack for single bracket type - O(1) space
Generate Parentheses: Backtracking with constraints: add '(' if open < n, add ')' if close < open - generates all valid combinations
Catalan Number: Number of valid n-pair parentheses = $C_n = \frac{1}{n+1}\binom{2n}{n}$ - fundamental counting result
Longest Valid DP: dp[i] = length of valid substring ending at i, handle '()' and '))' cases separately - O(n) time and space
DP Transitions: If s[i]=')' and s[i-1]='(': dp[i] = dp[i-2] + 2; if '))': check matching, add previous valid lengths
Stack for Longest: Track indices of unmatched brackets, length = current - index before unmatched portion - O(n) time/space
Two-Pass O(1): Left-to-right and right-to-left with counters, reset when imbalance - handles extra brackets on either side
Remove Invalid BFS: Level-by-level removal, stop at first valid level (minimum removals), use Set for deduplication
BFS Early Stop: Once valid strings found, don't explore deeper levels - guarantees minimum removal with BFS
Remove Backtracking: Pre-count invalid brackets, backtrack with removal budget, prune invalid paths during construction
Minimum Add: Track unmatched opening (need ')') and closing (need '('), sum is answer - O(n) time, O(1) space
Balance Method: Run counter, when negative add '(' and reset, final balance is unmatched '(' needing ')'

Related Cheat Sheets

Algorithm Patterns