[AlgoMastery]
Topics›String›Valid Parentheses/String
📖

Valid Parentheses/String

String
~20 min read
5 practice problems

Overview

Valid Parentheses/String problems involve checking if brackets, parentheses, and braces are properly matched and nested. These problems test your understanding of stack operations, string parsing, and pattern matching.

Key challenges:

  • Matching opening and closing brackets
  • Handling nested structures
  • Multiple bracket types
  • Minimum removals to make valid
  • Generating valid combinations

Common parentheses problems include:

  • Valid parentheses validation
  • Minimum removals to make valid
  • Generate parentheses combinations
  • Longest valid parentheses substring
  • Remove invalid parentheses
  • Score of parentheses

Pattern 1: Basic Valid Parentheses

Check if parentheses are properly matched.

Stack-based approach:

function isValidParentheses(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (const char of s) {
    if (pairs[char]) {
      // Closing bracket
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    } else if (char === '(' || char === '{' || char === '[') {
      // Opening bracket
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

Time: O(n), Space: O(n)

Counter-based (single type):

function isValidSingleType(s: string): boolean {
  let count = 0;
  
  for (const char of s) {
    if (char === '(') {
      count++;
    } else if (char === ')') {
      count--;
      if (count < 0) return false;
    }
  }
  
  return count === 0;
}

Time: O(n), Space: O(1)

Pattern 2: Minimum Removals to Make Valid

Find minimum removals to make parentheses valid.

function minRemoveToMakeValid(s: string): string {
  const stack: number[] = [];
  const toRemove = new Set<number>();
  
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else if (s[i] === ')') {
      if (stack.length > 0) {
        stack.pop();
      } else {
        toRemove.add(i);
      }
    }
  }
  
  // Remove unmatched opening parentheses
  while (stack.length > 0) {
    toRemove.add(stack.pop()!);
  }
  
  // Build result
  const result: string[] = [];
  for (let i = 0; i < s.length; i++) {
    if (!toRemove.has(i)) {
      result.push(s[i]);
    }
  }
  
  return result.join('');
}

Time: O(n), Space: O(n)

Two-pass approach:

function minRemoveToMakeValidTwoPass(s: string): string {
  // First pass: remove invalid ')'
  let result: string[] = [];
  let openCount = 0;
  
  for (const char of s) {
    if (char === '(') {
      openCount++;
      result.push(char);
    } else if (char === ')') {
      if (openCount > 0) {
        openCount--;
        result.push(char);
      }
    } else {
      result.push(char);
    }
  }
  
  // Second pass: remove invalid '('
  let finalResult: string[] = [];
  let closeCount = 0;
  
  for (let i = result.length - 1; i >= 0; i--) {
    if (result[i] === ')') {
      closeCount++;
      finalResult.unshift(result[i]);
    } else if (result[i] === '(') {
      if (closeCount > 0) {
        closeCount--;
        finalResult.unshift(result[i]);
      }
    } else {
      finalResult.unshift(result[i]);
    }
  }
  
  return finalResult.join('');
}

Pattern 3: Generate Parentheses

Generate all valid combinations of n pairs of parentheses.

function generateParentheses(n: number): string[] {
  const results: string[] = [];
  
  const backtrack = (current: string, open: number, close: number): void => {
    if (current.length === 2 * n) {
      results.push(current);
      return;
    }
    
    if (open < n) {
      backtrack(current + '(', open + 1, close);
    }
    
    if (close < open) {
      backtrack(current + ')', open, close + 1);
    }
  };
  
  backtrack('', 0, 0);
  return results;
}

Time: O(4^n / √n), Space: O(4^n / √n)

Iterative approach:

function generateParenthesesIterative(n: number): string[] {
  const results: string[] = [];
  const queue: Array<{str: string, open: number, close: number}> = [];
  
  queue.push({str: '', open: 0, close: 0});
  
  while (queue.length > 0) {
    const {str, open, close} = queue.shift()!;
    
    if (str.length === 2 * n) {
      results.push(str);
      continue;
    }
    
    if (open < n) {
      queue.push({str: str + '(', open: open + 1, close});
    }
    
    if (close < open) {
      queue.push({str: str + ')', open, close: close + 1});
    }
  }
  
  return results;
}

Pattern 4: Longest Valid Parentheses

Find length of longest valid parentheses substring.

Stack-based:

function longestValidParentheses(s: string): number {
  const stack: number[] = [];
  stack.push(-1); // Base for calculation
  let maxLength = 0;
  
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {
      stack.pop();
      
      if (stack.length === 0) {
        stack.push(i); // New base
      } else {
        maxLength = Math.max(maxLength, i - stack[stack.length - 1]);
      }
    }
  }
  
  return maxLength;
}

Time: O(n), Space: O(n)

Two-pointer approach:

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

Time: O(n), Space: O(1)

Pattern 5: Remove Invalid Parentheses

Remove minimum number of invalid parentheses to make string valid.

function removeInvalidParentheses(s: string): string[] {
  const results = new Set<string>();
  let minRemovals = Infinity;
  
  const backtrack = (
    current: string,
    index: number,
    open: number,
    close: number,
    removals: number
  ): void => {
    if (index === s.length) {
      if (open === close && removals <= minRemovals) {
        if (removals < minRemovals) {
          results.clear();
          minRemovals = removals;
        }
        results.add(current);
      }
      return;
    }
    
    const char = s[index];
    
    if (char !== '(' && char !== ')') {
      backtrack(current + char, index + 1, open, close, removals);
      return;
    }
    
    // Skip current character
    backtrack(current, index + 1, open, close, removals + 1);
    
    // Keep current character
    if (char === '(') {
      backtrack(current + char, index + 1, open + 1, close, removals);
    } else if (close < open) {
      backtrack(current + char, index + 1, open, close + 1, removals);
    }
  };
  
  backtrack('', 0, 0, 0, 0);
  return Array.from(results);
}

Time: O(2^n), Space: O(n)

Optimized with pruning:

function removeInvalidParenthesesOptimized(s: string): string[] {
  const results = new Set<string>();
  
  // Count invalid parentheses
  let leftRem = 0, rightRem = 0;
  for (const char of s) {
    if (char === '(') leftRem++;
    else if (char === ')') {
      if (leftRem > 0) leftRem--;
      else rightRem++;
    }
  }
  
  const backtrack = (
    current: string,
    index: number,
    leftCount: number,
    rightCount: number,
    leftRem: number,
    rightRem: number
  ): void => {
    if (index === s.length) {
      if (leftRem === 0 && rightRem === 0) {
        results.add(current);
      }
      return;
    }
    
    const char = s[index];
    
    // Skip character
    if ((char === '(' && leftRem > 0) || (char === ')' && rightRem > 0)) {
      backtrack(
        current,
        index + 1,
        leftCount,
        rightCount,
        leftRem - (char === '(' ? 1 : 0),
        rightRem - (char === ')' ? 1 : 0)
      );
    }
    
    // Keep character
    if (char !== '(' && char !== ')') {
      backtrack(current + char, index + 1, leftCount, rightCount, leftRem, rightRem);
    } else if (char === '(') {
      backtrack(current + char, index + 1, leftCount + 1, rightCount, leftRem, rightRem);
    } else if (rightCount < leftCount) {
      backtrack(current + char, index + 1, leftCount, rightCount + 1, leftRem, rightRem);
    }
  };
  
  backtrack('', 0, 0, 0, leftRem, rightRem);
  return Array.from(results);
}

Pattern 6: Score of Parentheses

Calculate score based on parentheses nesting.

function scoreOfParentheses(s: string): number {
  const stack: number[] = [];
  let score = 0;
  
  for (const char of s) {
    if (char === '(') {
      stack.push(score);
      score = 0;
    } else {
      score = stack.pop()! + Math.max(2 * score, 1);
    }
  }
  
  return score;
}

Time: O(n), Space: O(n)

Recursive approach:

function scoreOfParenthesesRecursive(s: string): number {
  return scoreHelper(s, 0, s.length - 1);
}

function scoreHelper(s: string, left: number, right: number): number {
  if (right - left === 1) return 1; // "()"
  
  let balance = 0;
  
  for (let i = left; i < right; i++) {
    if (s[i] === '(') balance++;
    else balance--;
    
    if (balance === 0) {
      // Balanced split
      return scoreHelper(s, left, i) + scoreHelper(s, i + 1, right);
    }
  }
  
  // Nested case: (A) = 2 * A
  return 2 * scoreHelper(s, left + 1, right - 1);
}

Pattern 7: Valid Parentheses with Wildcards

Check validity when '*' can represent '(', ')', or empty.

function checkValidString(s: string): boolean {
  let minOpen = 0, maxOpen = 0;
  
  for (const char of s) {
    if (char === '(') {
      minOpen++;
      maxOpen++;
    } else if (char === ')') {
      minOpen = Math.max(0, minOpen - 1);
      maxOpen--;
      if (maxOpen < 0) return false;
    } else { // '*'
      minOpen = Math.max(0, minOpen - 1);
      maxOpen++;
    }
  }
  
  return minOpen === 0;
}

Time: O(n), Space: O(1)

Pattern 8: Different Bracket Types

Handle multiple types of brackets.

function isValidMultipleBrackets(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ')': '(',
    '}': '{',
    ']': '[',
    '>': '<'
  };
  
  for (const char of s) {
    if (pairs[char]) {
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    } else if (Object.values(pairs).includes(char)) {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

Custom bracket pairs:

function isValidCustomBrackets(
  s: string, 
  openBrackets: string[], 
  closeBrackets: string[]
): boolean {
  const stack: string[] = [];
  const openSet = new Set(openBrackets);
  const closeToOpen = new Map<string, string>();
  
  for (let i = 0; i < openBrackets.length; i++) {
    closeToOpen.set(closeBrackets[i], openBrackets[i]);
  }
  
  for (const char of s) {
    if (openSet.has(char)) {
      stack.push(char);
    } else if (closeToOpen.has(char)) {
      if (stack.length === 0 || stack.pop() !== closeToOpen.get(char)) {
        return false;
      }
    }
  }
  
  return stack.length === 0;
}

Pattern 9: Count Valid Parentheses Substrings

Count number of valid parentheses substrings.

function countValidSubstrings(s: string): number {
  let count = 0;
  
  for (let i = 0; i < s.length; i++) {
    let balance = 0;
    
    for (let j = i; j < s.length; j++) {
      if (s[j] === '(') balance++;
      else balance--;
      
      if (balance < 0) break;
      if (balance === 0) count++;
    }
  }
  
  return count;
}

Time: O(n^2), Space: O(1)

Optimized:

function countValidSubstringsOptimized(s: string): number {
  let count = 0;
  const dp: number[] = new Array(s.length).fill(0);
  
  for (let i = 1; i < s.length; i++) {
    if (s[i] === ')') {
      if (s[i - 1] === '(') {
        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
      } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
        dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
      }
      count += dp[i] > 0 ? 1 : 0;
    }
  }
  
  return count;
}

Pattern 10: Minimum Additions to Make Valid

Find minimum additions needed to make parentheses valid.

function minAddToMakeValid(s: string): number {
  let openNeeded = 0;
  let closeNeeded = 0;
  
  for (const char of s) {
    if (char === '(') {
      closeNeeded++;
    } else if (char === ')') {
      if (closeNeeded > 0) {
        closeNeeded--;
      } else {
        openNeeded++;
      }
    }
  }
  
  return openNeeded + closeNeeded;
}

Time: O(n), Space: O(1)

Pattern 11: Check if String Can Be Valid

Check if string can be made valid by swapping characters.

function canBeValid(s: string, locked: string): boolean {
  if (s.length % 2 !== 0) return false;
  
  let open = 0, close = 0, unlocked = 0;
  
  // Left to right
  for (let i = 0; i < s.length; i++) {
    if (locked[i] === '0') {
      unlocked++;
    } else if (s[i] === '(') {
      open++;
    } else {
      close++;
    }
    
    if (close > open + unlocked) return false;
  }
  
  open = close = unlocked = 0;
  
  // Right to left
  for (let i = s.length - 1; i >= 0; i--) {
    if (locked[i] === '0') {
      unlocked++;
    } else if (s[i] === ')') {
      close++;
    } else {
      open++;
    }
    
    if (open > close + unlocked) return false;
  }
  
  return true;
}

Time: O(n), Space: O(1)

Pattern 12: Maximum Nesting Depth

Find maximum nesting depth of valid parentheses.

function maxDepth(s: string): number {
  let maxDepth = 0;
  let currentDepth = 0;
  
  for (const char of s) {
    if (char === '(') {
      currentDepth++;
      maxDepth = Math.max(maxDepth, currentDepth);
    } else if (char === ')') {
      currentDepth--;
    }
  }
  
  return maxDepth;
}

Time: O(n), Space: O(1)

For nested structures:

function maxNestingDepth(s: string): number {
  let maxDepth = 0;
  const stack: number[] = [];
  
  for (const char of s) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(1);
      maxDepth = Math.max(maxDepth, stack.length);
    } else if (char === ')' || char === '}' || char === ']') {
      if (stack.length > 0) {
        stack.pop();
      }
    }
  }
  
  return maxDepth;
}

When to Use Parentheses Techniques

Use parentheses validation when:

  • Problem mentions "valid parentheses", "brackets", or "braces"
  • Need to match opening/closing pairs
  • Nested structures validation
  • Minimum operations to make valid
  • Generate combinations of parentheses
  • Calculate scores based on nesting

Template (Stack-based)

function isValidParenthesesTemplate(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (const char of s) {
    if (pairs[char]) {
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    } else if (Object.values(pairs).includes(char)) {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

Template (Counter-based)

function isValidCounterTemplate(s: string): boolean {
  let count = 0;
  
  for (const char of s) {
    if (char === '(') count++;
    else if (char === ')') {
      count--;
      if (count < 0) return false;
    }
  }
  
  return count === 0;
}

Time and Space Complexity Summary

  • Basic validation: O(n) time, O(n) space (stack), O(1) space (counter)
  • Minimum removals: O(n) time, O(n) space
  • Generate parentheses: O(4^n / √n) time, O(4^n / √n) space
  • Longest valid: O(n) time, O(n) space (stack), O(1) space (two-pointer)
  • Remove invalid: O(2^n) time, O(n) space
  • Score calculation: O(n) time, O(n) space

Practice Tips

  1. Use stack — For multiple bracket types
  2. Use counter — For single type, space-efficient
  3. Process right to left — For some problems
  4. Track balance — Count open vs close
  5. Handle edge cases — Empty strings, all open/close
  6. Prune early — In backtracking solutions

Common Mistakes

  1. Not checking stack empty — Before popping
  2. Wrong bracket matching — Verify pairs correctly
  3. Off-by-one errors — Careful with indices
  4. Not resetting counters — In nested loops
  5. Missing base cases — In recursive solutions

Related Concepts

  • Stack Operations — For bracket matching
  • String Parsing — Processing bracket strings
  • Backtracking — For generating combinations
  • Dynamic Programming — For optimization problems

Valid parentheses problems are fundamental in string algorithms. Master these patterns, and you'll be well-prepared for bracket-related interview questions.

← PreviousBackspace String CompareNext →Word Break Problems