Daily bit(e) of C++ | Longest string with valid parenthesis

Daily bit(e) of C++ #329, Common interview problem: Longest string with valid parenthesis.

Today, we will look at a common C++ interview problem: Longest string with valid parenthesis.

Given a string that contains parentheses '(',')' intermixed with other characters, return the longest string (formed by removing some characters) that contains only valid parentheses. If there are multiple such strings, return any.

For example, for the string “()))(a((b)()c(()(“, one possible result is “()a(b)()c()”, however, “()a((b)()c)” is also valid.

Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/Y7MMGWGhc.

Solution

If we do a left-to-right pass, we can filter out excessive ‘)’ parenthesis by ensuring enough preceding left parenthesis. And we can apply the same logic in the inverse direction.

So, one solution would be to process the string twice using the above logic. However, we can do slightly better. Once we scan the string, we know how many parentheses are remaining and, therefore, how many we must remove.

The second observation is that if we are processing left-to-right and have excessive ‘)’ parentheses, it is always correct to remove the earliest instances. And again, the same logic applies to the left parenthesis when processing in the opposite direction.

Putting this all together, we can do all processing in place. First, we process right-to-left, removing excessive ‘(‘ parenthesis, then left-to-right, moving the string back into position (starting at index zero), removing the leading excessive ‘)’ parenthesis.

Click to open in Compiler Explorer.

---