Gfyuki

I was given the following problem during an interview:

Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all parens that have no matching paren.

For example, in the string ")(ab))", indices 0 and 5 contain parens that have no matching paren.

I put forward a working O(n) solution using O(n) memory, using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren.

Afterwards, the interviewer noted that the problem could be solved in linear time with constant memory (as in, no additional memory usage besides what's taken up by the input.)

I asked how and she said something about going through the string once from the left identifying all open parens, and then a second time from the right identifying all close parens....or maybe it was the other way around. I didn't really understand and didn't want to ask her to hand-hold me through it.

Can anyone clarify the solution she suggested?

Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $Theta(log(n))$ memory to store an index into a string of length $n$.

You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.

using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren

So what does this stack contain? It's never going to contain () (an opening parenthesis followed by a closing parenthesis), since whenever the ) appear you pop the ( instead of pushing the ). So the stack is always of the form )…)(…( — a bunch of closing parentheses followed by a bunch of opening parentheses.

You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.

If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.

If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.

In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.

The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.

Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).

Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.

Since we can just ignore all alphanumeric characters, we will assume the string contains only parentheses from now on. As in the question, there is only one kind of parenthesis, "()".

If we keep removing balanced parentheses until no more balanced parentheses can be removed, all remaining parentheses must look like like "))…)((…(", which are all unbalanced parentheses. This observation suggests that we should find first that turning point, before which we have unbalanced closing parentheses only and after which we have unbalanced opening parentheses only.

Here is the algorithm. In a nutshell, it computes the turning point first. Then it outputs extra closing parenthesis, scanning the string from the start to the right until the turning point. Symmetrically, it outputs extra opening parenthesis, scanning from the end to the left until the turning point.

Let str be the string as an array of characters, whose size is $n$.

Initialize turning_point=0, maximum_count=0, count=0. For each i from 0 to n-1 do the following.

1. If str[i] = ')', add 1 to count; otherwise, subtract 1.


2. If count > maximum_count, set turning_point=i and maximum_count=count.

Now turning_point is the index of the turning point.

Reset maximum_count=0, count=0. For each i from 0 to turning_point do the following.

1. If str[i] = ')', add 1 to count; otherwise, subtract 1.


2. If count > maximum_count, set maximum_count = count. Output i as the index of an unbalanced closing parenthesis.

Reset maximum_count=0, count=0. For each i from n-1 to turning_point+1 downwards do the following.

1. If str[j] = '(', add 1 to count; otherwise, subtract 1.


2. If count > maximum_count, set maximum_count = count. Output i as the index of an unbalanced opening parenthesis.

It is clear that the algorithm runs in $O(n)$ time and $O(1)$ auxiliary memory and $O(u)$ output memory, where $u$ is the number of unbalanced parentheses.

If we analyzed the algorithm above, we will see that, in fact, we do not need to find and use the turning point at all. The nice observation that all unbalanced closing parentheses happens before all unbalanced opening parentheses can be ignored although interesting.

Here is code in Python.

Just hit "run" to see several test results.

Exercise 1. Show that the above algorithm will output a set of parentheses with the least cardinality such that the remaining parentheses are balanced.

Problem 1. Can we generalize the algorithm to the case when the string contains two kinds of parentheses such as "()"? We have to determine how to recognize and treat the new situation, the interleaving case, "([)]".