We will explore algorithms to find the Minimum number of operations to convert a binary string to a self-destructing string.

What is a self-destructing string?

A binary string is called a self-destructing string if it can reduced to an empty string by performing the following operation 0 or more times:

"Choose a valid integer i such that the i-th character of the current string is different from the i+1-th character, and remove these two characters from the string."

The Problem

Given a binary string str, the task is to convert str to a self-destructing string. This may be achieved by performing the following operation 0 or more times:

"Choose an integer i such that the i-th character of str is different from the i+1-th character, and invert one of these characters (inverting a character means changing '0' to '1' or '1' to '0', for example, the string "10" can be changed to "11")."

Find the smallest number of operations required to convert str to a self-destructing string or determine that it is impossible.

NOTE: The output is taken as -1, if it is impossible to convert the given binary string to a self-destructing string.

Example 1:

Input:
str = "100110"
Output:
0
Explanation:
Observe that the given string is
already self-destructing.
Verifying,
Remove 10 from 100110.
100110 -> 0110
Remove 01 from 0110.
0110 -> 10
Remove 10 from 10.
10 -> Empty string

Example 2:

Input:
str = "1101"
Output:
1
Explanation:
Take the pair 10 from 1101.
Change 10 to 00.
Now the string becomes,
1101 -> 1001
"1001" is self-destructing.

Example 3:

Input:
str = "101"
Output:
-1
Explanation:
In a self-destructing string,
a pair is removed at a time.
Assuming the given string 
to be self-destructing,
if the string is of odd
length, a single character will
always remain after removing all pairs.
Hence, it cannot be self-destructing.

Example 4:

Input:
str = "1111"
Output:
-1
Explanation:
Since, there are only '1's
in the given string,
a pair with different characters
can never be selected.
Hence, it can never become
self-destructing.

Observations:

From our examples above, we observe that:

• A self-destructing string must have equal number of '0's and '1's.
• A binary string of odd length can never be a self-destructing string.
• If a binary string has only '0's or only '1's, it cannot be converted to a self-destructing string.
• Making another observation using point 2 and 3, if a binary string is of even length and contains at least one '0' and at least one '1', then it can be converted to a self-destructing string.

Approach:

• Check if the string is of odd length. If the length is odd, print -1.
• Check if the string contains only '0's or only '1's. If it does, print -1.
• If the first two conditions fail, we can be sure that the given string can be converted to a self-destructing string by performing the operation 0 or more times.
  We know that the number of '0's and '1's must be equal in a self-destructing string, i.e. in a string of length n. there must be n/2 '0's and n/2 '1's. We count the number of '0's (or '1's), and take the absolute difference of n/2 and the count of '0's (or '1's). This gives the required number of operations.

Basically, point 4 can also be written as, "subtracting the number of '0's (or '1's) we actually have from the number of '0's (or '1's) we actually need or vice-versa".

Example 2 with the above approach

Input:
str = "1101"
Approach:
Check if the string is of odd length -> NO
Check if there are only 0's or only 1's -> NO
The first two conditions fail, 
str can be converted to
a self-destructing string.
Count the no. of 1's, count = 3
Length of str, n = 4
(n/2) - count = 4 - 3 = 1
Output:
1

Try the approach with the other examples before looking at the solution!

Solution:

C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string str = "1011";
    int n = str.length();
    // check if the string
    // is of odd length
    if (n % 2 == 1) {
        cout << "-1" << endl;
    }
    else {
        int count = 0;
        // count the
        // number of '1's
        for (auto ch : str) {
            if (ch == '1')
                count++;
        }
        // check if only '1's
        // or no '1's are present
        if (count == n || count == 0) {
            cout << "-1" << endl;
        }
        else {
            cout << abs(n / 2 - count) << endl;
        }
    }
}

Output:

1

Time Complexity: Since, there is only one loop involved, the worst case time complexity would be O(n).
Space Complexity: No auxiliary space is used, so the space complexity is O(1),