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