Algorithms 4: Symmetry in Parentheses

'Tis the season for interviews and career preparation.

So without further ado, let's do a welcome back post!

Problem. Given an input string $s$ of length $n$ containing only left and right parentheses, determine whether or not it is a valid parenthetical expression.

By definition, a parenthetical expression is valid if every left parenthesis has a corresponding closing right parenthesis, and every right parenthesis has a corresponding opening left parenthesis.

Solution.

There are a few key things to note about validating a parenthetical expression. One is the trivial case, where $s$ is an empty string. The empty string is always valid.

Another case is where the string is of odd length. We know that for the string to be valid, it must contain the same number of left and right parentheses and have even length. An odd-length string is never valid.

Then comes the more tricky intuition. If you've worked with the shunting yard algorithm or used stacks to determine whether a string is balanced, you might be inclined to use a stack for this problem.

This is somewhat of a trap, because the ideal solution actually uses constant space. Because this problem is one of symmetry, we can actually employ a conservation approach. Let $\phi = 0$ indicate the net value. Iterate through the string each character at a time, adding $1$ to $\phi$ whenever we see a left paren and subtracting $1$ whenever we see a right paren. Note that if $\phi < 0$ at any point in the iteration, we have an invalid string.

	def isValid(s):
    	"""
        Given a string containing only parentheses,
        returns whether it is valid or not.
        """
        if len(s) == 0:
        	return True
        if len(s) % 2 > 0:
        	return False
        count = 0
        for i in range(0, len(s)):
        	count += 1 if s[i] == '(' else -1
            if count < 0:
            	return False
		return count == 0

This algorithm runs in linear time and constant space, without modifying the input string.

Once you've solved the above, the question extends to the following:

Problem. Given the input string from the above problem, determine the minimum number of flip operations required to make $s$ a valid parenthetical expression. Return $-1$ if this is not possible.

We adapt our solution from above, with the addition of another variable to count the number of flips needed, $numFlips$. We iterate through the string, if during our iteration we get a negative $\phi$, this indicates the need for an implicit 'flip' operation. We then increment $numFlips$ and set $\phi = 1$, continuing the iteration. When finished iterating, for however many $\phi$ left parens are not matched, we flip half of those parens.

Why does this work? Because whenever $\phi$ is $-1$, we set it to $1$ and perform a flip operation, we will never have a $\phi < -1$. Additionally, because we've already checked to ensure that the length of the string is even, we can guarantee that a valid string may be formed from $s$. If $\phi > 0$ by the end of the algorithm, then it therefore must be even and we can flip $\phi/2$ parens.

	def numFlipsNeeded(s):
    	if len(s) == 0:
        	return 0
        if len(s) % 2 > 0:
        	return -1
        count = 0
        numFlips = 0
        for i in range(0, len(s)):
        	count += 1 if s[i] == '(' else -1
            if count < 0:
            	numFlips += 1
                count = 1
		numFlips += count/2
        return numFlips

The above code runs in linear time and still uses only constant space! Awesome.

That's it for today. If there are any questions or errata, leave a comment!