# Valid Parentheses

Stack Easy LeetCode #20

## 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.