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?
Greedy algorithms - minimising parentheses rotatons in order to get a valid expression
algorithms