O(2n), samo che ne bachka, shtoto ne hvashta vryshta "))((" vmesto empty str

min-valid-paren.rb

# @param {String} s
# @return {String}
def min_remove_to_make_valid(s)
  chars = s.split('')
  op = chars.reduce(0) { |a, c| a + (c == '(' ? 1 : 0) }
  cl = chars.reduce(0) { |a, c| a + (c == ')' ? 1 : 0) }
  diff = op - cl
  chars.select do |c|
    if diff === 0
      true
    elsif diff > 0
      if c === '('
        diff -= 1
        false
      else
        true
      end
    else
      if c === ')'
        diff += 1
        false
      else
        true
      end
    end
  end.join('')
end

puts min_remove_to_make_valid("(a(b(c)d)")
puts min_remove_to_make_valid("lee(t(c)o)de)")
puts min_remove_to_make_valid("a)b(c)d")
puts min_remove_to_make_valid("))((")
puts min_remove_to_make_valid("(a(b(c)d)")
puts min_remove_to_make_valid("a(b(c)d)")