Balanced parenthesis in Ruby
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 = { '{' =&gt; '}', '[' =&gt; ']', '(' =&gt; ')' }

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

  stack.empty?
end