Count the Reversals

Given a string S consisting of only opening and closing curly brackets '{' and '}', find out the minimum number of reversals required to convert the string into a balanced expression.
A reversal means changing '{' to '}' or vice-versa.

Example 1:

Input:
S = "}{{}}{{{"
Output: 3
Explanation: One way to balance is:
"{{{}}{}}". There is no balanced sequence
that can be formed in lesser reversals.

Example 2:

Input: 
S = "{{}{{{}{{}}{{"
Output: -1
Explanation: There's no way we can balance
this sequence of braces.



method 1 :

use sorting:

sort both the string now check if the sorted strings are equal if they are equal return 1, else return 0.

c++ implementation:

int minimumNumberOfSwaps(string s){
    int l = s.length();
 
    if (l%2)
    return -1;
    stack<char> st;

    for (int i=0; i<l; i++)
    {
        if (s[i]=='}' && !st.empty() && st.top()=='{')
                st.pop();
            else
                st.push(s[i]);
    }
    
    int w = st.size();
    int n = 0;
    while (!st.empty() && st.top() == '{')
    { 
      st.pop();
      n++;
    }
 
  int m=w-n;
   if(m%2!=0)
     m++;
   if(n%2!=0)
    n++;

    return (m/2+n/2);
    }


Time Complexity: O(n) 
space Complexity: O(n) 




darkmode