Given a string with opening and closing braces, our problem is to find the minimum number of operations to make the string stable. This can be solved efficiently using Stack. A string is stable based on the following rules:

• An empty string is stable.
• If S is stable, then {S} is also stable.
• If S and T are both stable, then the concatenation of S and T is stable (that is ST).
• All of these strings are stable: {}, {}{}, and {{}{}}
• These strings are not stable: }{, {{}{, nor {}{.

Two operations are allowed on the string:

• replace an opening brace with a closing brace
• replace an closing brace with a opening brace

This is the SPOJ Problem ANARC09A (Seinfeld).

Handling input

We are not given the number of test cases right infront of the input. Instead the input terminates with one or more '-' signs. To handle that we can use an infinite while loop and break out of it as soon as we get a '-' sign.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    while(true) {
        cin >> S;
        if (S[0]=='-') break;
        // main logic here
    }
    return 0;
}

Handling Output

Also note that in output we need to print the line number corresponding to minimum number of operations. For that we can simply use a counter. We are storing operations in a variable named op.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    int count = 1;
    while(true) {
        cin >> S;
        if (S[0]=='-') break;
        int op = 0;
        
        // main logic here
        
        cout << count++ << ". " << op << endl;
    }
    return 0;
}

Notice how we are incrementing count by one each time while printing it on the same line.

Main Logic

We can iterate through the string use a stack to keep track of balanced expressions. Each time a { appears we push it to the stack and pop when a } appears.

If the stack is empty and a closing bracket appears, we can say that it is unbalanced (because there is no matching opening bracket corresponding to it) and convert it to an opening bracket.

Hence incrementing the number of operations (op) by one. We'll also need to push the push the converted bracket to the stack.

After completely iterating over the string we just convert half the remaining elements ({) of the stack into closing brackets and update op accordingly.

Notice that we are pushing only one type of entity in the stack ({). So instead we can just use a counter initially set to zero (empty condition). Incrementing it will denote pushing an element and decrementing will denote popping an element. Here we'll call our counter bal (short for balance). Here is the final code -

// Part of iq.OpenGenus.org
#include <bits/stdc++.h>
using namespace std;

int main() 
{
    string S;
    int count = 1;
    // While loop for taking input
    while(true) 
    {
        cin >> S;
        if (S[0]=='-') 
            break;
            
        // Main logic
        int op = 0, bal = 0;
        for (int i=0; i<S.size(); i++) 
        {
            if(S[i]=='{') 
                bal++;
            else 
                bal--;
            if (bal<0) 
            {
                op++;
                bal += 2;
            }
        }
        op += bal/2;
        cout << count++ << ". " << op << endl;
    }
    return 0;
}

Time & Space complexity

The time complexity is O(N)
The space complexity is O(1)

where

• N is the number of characters in the input string.

Note that the problem is tagged under dynamic programming on SPOJ. Do comment under this article if you want to share that approach. And check out our other articles on C++ STL and algorithms to get better ar problem solving. You can also implement the above logic in python as a fun exercise.

With this article at OpenGenus, you must have the complete idea of how to find the minimum number of operations to make a string stable.