Get this book -> Problems on Array: For Interviews and Competitive Programming

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),