Valid Parentheses

Problem

Given a string s containing just the characters (, ), {, }, [, and ], determine if the input string is valid.

A string is valid if:

• Open brackets are closed by the same type of bracket.
• Open brackets are closed in the correct order.
• Every close bracket has a corresponding open bracket of the same type.

Approach 1: Brute Force (Repeated Removal)

Repeatedly remove inner-most matched pairs until the string is empty or no more removals can be made.

def is_valid(s)
  loop do
    prev = s.length
    s = s.gsub("()", "").gsub("[]", "").gsub("{}", "")
    return true if s.empty?
    return false if s.length == prev
  end
end

Time: O(n^2) – each pass removes at most one nesting level, and each pass scans the string.

Space: O(n) – intermediate string copies.

Approach 2: Stack (Optimal)

Push opening brackets onto a stack. When you encounter a closing bracket, check that it matches the top of the stack.

def is_valid(s)
  stack = []
  match = { ")" => "(", "]" => "[", "}" => "{" }

  s.each_char do |c|
    if match.key?(c)
      return false if stack.empty? || stack.last != match[c]
      stack.pop
    else
      stack.push(c)
    end
  end

  stack.empty?
end

Time: O(n) – single pass, each character is pushed and popped at most once.

Space: O(n) – stack holds up to n/2 opening brackets in the worst case.

Key Takeaway

A stack naturally models “most recent first” matching. Any problem involving nested or balanced structures (brackets, HTML tags, directory paths) is a strong signal to reach for a stack.