Balanced parenthesis in Ruby

I’m solving the “Balanced Parenthesis” problem in Ruby, and I came up with this solution.

def balanced?(string)
  return false if string.length.odd?

  pairs = { '{' => '}', '[' => ']', '(' => ')' }

  string.chars.each_with_object([]) do |bracket, stack|
    if pairs.keys.include?(bracket)
      stack << bracket
    elsif pairs.values.include?(bracket)
      return false unless pairs[stack.pop] == bracket
    else
      return false
    end
  end

  true
end

The first check is for the length of the string: If it’s odd, the can’t be balanced.

I then iterate over the chars of the string:

1. If I find an opening bracket, I add it to an array.
2. If I find a closing bracket, I remove the last element from the array and check if the brackets are a pair.
3. If I find neither an opening or a closing bracket, the string must be invalid.

Are there any edge cases I’m missing? Also, this doesn’t seem efficient: First, there’s an added dictionary. Second, there is a linear search on each iteration to check either the keys or the values of the dictionary. There’s an $O(n)$ on the array resulting from the string, as well, but I’m not sure if we can avoid this.

To eliminate nested loop you may apply regex checking for invalid symbol from the start — it would be O(n) + O(n) = O(n):

def balanced? string
  return false if string.length.odd?
  return false if string =~ /[^[](){}]/

  pairs = { '{' => '}', '[' => ']', '(' => ')' }

  stack = []
  string.chars do |bracket|
    if expectation = pairs[bracket]
      stack << expectation
    else
      return false unless stack.pop == bracket
    end
  end

  stack.empty?
end

Assuming it’s possible to check each pair separately:

def is_balanced(opener, closer, str)
  cnt = 0
  adds = {opener => 1, closer => -1}
  pars = str.chars.select{|c| [opener, closer].include? c }
  pars.each{ |c| cnt += adds[c]; return false if cnt < 0 }
  cnt == 0
end

def is_balanced2(str)
  [['(', ')'], ['[', ']'], ['{', '}']].map{ |ps| is_balanced(*ps, str) }.all?
end

Constant Time solution, assuming you know the paren chars:

    def is_valid(str)
        characters = [
            '(', ')',
            '{', '}', 
            '[', ']',
        ]
       
        if str.count(characters[0]) != str.count(characters[1])
            return false
        end
    
        if str.count(characters[2]) != str.count(characters[3])
            return false
        end
    
        if str.count(characters[4]) != str.count(characters[5])
            return false
        end
    
        true
    end

Its beautifully simple.