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.
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.
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.
The time and space complexity of the proposed solution are both
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
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
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
The fourth and last position is an opening parenthesis. We remember
that parenthesis in
op like before.
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
dl. By doing so we get string
(), a balanced string with
the minimum number of parentheses removed.
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?