a bit of string balancing: SPOJ - ANARC09A

Problem Statement:
SPOJ - ANARC09A

Summary:
Given a string consisting of open and close brackets, find the number of operations needed to balance the brackets. An operation is defined as flipping a bracket. Balanced is in the usual sense: if S,T is balanced, then {}, {S}, ST are all balanced.

Solution:
I used DP approach which is quite expensive in terms of running time and memory, the idea is to keep track of the number of open brackets.
Let S(k, open) be the number of min operations to balance the string
with |open| open brackets by the time we start at k.
Let current bracket be cur. We have several cases:
1. open is 0, and cur = '}', then we have to flip.
   S(k, open) = 1 + S(k+1, open+1)
   open is 0 and cur = '{', then we cannot flip.
   S(k, open) = S(k+1, open+1)

2. open > 0 and cur = '}'. We can use cur to close an open bracket, or
   flip it to add new open brackets.
   S(k, open) = min( S(k+1, open-1), 1 + S(k+1, open+1) )
3. open > 0 and cur = '{', then we have
   S(k, open) = min( S(k+1, open+1), 1 + S(k+1, open-1) )
Then the implementation is standard DP with \(O(N^2)\) running time. However, the problem can be solved in O(N) time!
Firstly, we do exactly the same thing: proceeding from left to right, we keep track of the number of open brackets. When we encounter '}', we greedily close any open brackets we have, but if we don't have any open brackets left, we have to flip that bracket and incur a cost. Otherwise, whenever we encounter '{', we add it to total open brackets. After we iterate through the brackets, we will have O open brackets and C costs incurred. The minimum operations required is then C + O/2! (since we just need to flip half of the open brackets to balance them)