Greedy algorithms - minimising "parentheses rotatons" in order to get a valid expression

Question

I'm preparing for an exam on which there will be problems solvable by DP, greedy algorithms. And one of the problem is - given a string containing parentheses in no particular order return a minimum number of "rotations" needed to make a valid expression, for example ())) is not a valid expression but you can "rotate" second paren to get (()) which is a valid expression (the answer would then be 1).

I've been told this can be solved with some greedy algorithm. It's quity easy to find O(n^3) DP solution so we're looking for something else (possibly O(n)?). What is the strategy when trying to find a greedy solution for such problem?

Answer 1

Greedy means take the action that immediately tries to improve the problem.

You replace each \() pair that encloses only periods . with periods. Then eventually you will end up with the a sequence of closing parens followed by a sequence of open parens (interspersed by periods).

Then you just need to rotate the first half of the closing parens and the second half of the open parens.

The last step will be to fix the )( case so it becomes the proper ().

This is O(n²) with a naive matching algorithm. Though it can be sped up by thinking of the replace step as expanding the period runs.

Answer 2

I haven't solved this particular problem, but there's a general approach to take. The first thing to look at is what information you can calculate in O(n). In this case:

• The count of open and close parens.
• The absolute minimum number of rotations, based on uneven count.
• The current depth of nesting of each paren, starting from the right and left side of the string.
• The maximum allowed nesting depth at any point, based on the remaining opposite parens available, starting from the right and left side of the string.
• Which parens are already properly balanced.

Then you solve a bunch of test cases manually, and look at the above calculated information for the parens you flip. Try comparing, subtracting, adding, etc. the parameters you calculated. Are there any patterns you can discern? Can you figure out how to adjust the calculated information in O(1) after you perform a flip?

This part takes a certain amount of practice. It can help to go through the exercise for known algorithms, trying to "reverse engineer" them.