You are given a string that may contain any number of parentheses “(“ and “)”. Remove from the string the minimum number of parentheses so that the remaining parentheses are balanced.

Consider the following examples.

"()())()" -> "()()()" or "(())()"
"(bla)(ble))(bli)" -> "(bla)(ble)(bli)" or "(bla(ble))(bli)"
")(" -> ""
")))" -> ""

Input. The input file consists of one or more input strings, each on a single line. The input file is terminated by an EOF character. Consider the following example.

()())()
(bla)(ble))(bli)
)(
)))
(helo)())
(((((
(((()((
)()

Output. The output file consists of an output string for each input line, each on a separate line. For example, the following output corresponds to the previous example input.

()()()
(bla)(ble)(bli)



(helo)()

()
()

Solution

The time and space complexity of the proposed solution are both O(n).

Consider the string ())( from left to right. Given that the first position is an opening parenthesis, remember that position in stack of opening parentheses that are unmatched op.

    ())(
0123
|
V
op: 0

The second position is a closing parenthesis. We match it with the opening parenthesis that we found before and therefore remove the opening parenthesis from op.

    ())(
0123
*
op:

The third position is again a closing parenthesis. This time we don’t have an opening parenthesis that matched and so we remember this position for later deletion in list dl.

    ())(
0123
|
V
dl: 2
op:

The fourth and last position is an opening parenthesis. We remember that parenthesis in op like before.

    ())(
0123
|
V
dl: 2
op: 3

We don’t have any more parenthesis to match that last opening parenthesis because we are at the end of the string. So, it makes sense to remove that last opening parenthesis together with anything in list dl. By doing so we get string (), a balanced string with the minimum number of parentheses removed.

Ruby implementation

#!/usr/bin/env ruby

def balance s

op = [] # opening parentheses
dl = [] # delete these indexes later

s.chars.each_with_index do |c, i|
if c == '(' # `c` is an opening parenthesis
op << i # that we have to remember.
elsif c == ')' # `c` is a closing parenthesis
if op.length == 0 # that does not match an opening parenthesis
dl << i # and therefore we will delete later
else # that corresponds to an opening parenthesis
op.pop # and therefore we forget about both
end
end
end
dl += op # delete later all unmatched opening/closing parentheses

r = '' # result string
di = 0 # index in dl
s.chars.each_with_index do |c, i|
if di < dl.length and dl[di] == i # either skip this character
di += 1
else # or not
r += c
end
end

return r
end

while true
s = readline.strip rescue break
puts balance s
end

Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments