Valid Parentheses

Difficulty: Easy

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.

Example

Input: s = "({[]})"
Output: true
Explanation: Each opening bracket is closed by its matching bracket in the correct order: [ ] is matched, then { } wraps it, then ( ) wraps everything.

Brute-force approach

Repeatedly scan the string and remove adjacent matching pairs '()', '[]', '{}' until no more can be removed. If the string becomes empty, it's valid.

Steps

  1. While the string contains '()', '[]', or '{}':
  2. Replace all occurrences of '()', '[]', '{}' with empty string
  3. If the string is now empty, return true
  4. Otherwise return false

Time complexity: O(n²) · Space complexity: O(n)

Trade-offs

  • Each pass through the string is O(n), and we may need up to n/2 passes
  • String replacement creates new strings each time
  • Inefficient for long strings with deeply nested brackets

Optimal approach

Key insight: The last opened bracket must be the first one closed — a perfect fit for a stack's LIFO behavior.

Use a stack: push opening brackets, and for each closing bracket check if it matches the top of the stack. If all match and the stack is empty at the end, the string is valid.

Steps

  1. Create a map: ')' → '(', ']' → '[', '}' → '{'
  2. Initialize an empty stack
  3. For each character in the string:
  4. If closing bracket: check stack top matches, pop if yes, return false if no
  5. If opening bracket: push onto stack
  6. Return true if stack is empty, false otherwise

Time complexity: O(n) · Space complexity: O(n)