# Minimum steps to make binary string empty by removing alternating subsequence in each step

Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

Given a string **str** consisting of only '0's and '1's, the task is to make the string empty by performing minimum number of operations. An operation is defined as the removal of an alternating subsequence from **str** without changing the order of the remaining characters. An alternating subsequence is defined as any subsequence in **str**, of at least length 1, where no two consecutive characters are equal. Ex: "0", "1", "10", "01", "101", etc.

## Examples

```
Input: str = "1011"
Output: 2
Explanation:
In the first step, the subsequence "101" is removed.
1011 -> 1
In the second step, the subsequence "1" is removed.
1 -> NULL
```

```
Input: str = "0100100111"
Output: 3
Explanation:
In the first step, the subsequence "010101" is removed.
0100100111 -> 0011
In the second step, the subsequence "01" is removed.
0011 -> 01
In the third step, the subsequence "01" is removed.
01 -> NULL
```

## Observation

It can be observed that whenever there are two equal consecutive characters in **str**, i.e. "00" or "11", at least two operations need to be performed to make str empty. If there are three consecutive equal characters, at least three operations need to be performed, and so on.

Hence, the problem can be reduced to finding the maximum among the lengths of the longest substrings of 0 and 1.

The above examples can now be solved using this observation. Try it yourself!

**NOTE:** A substring is a continuous group of characters. A subsequence may or may not be continuous.

## Approach

- Maintain three variables, one for the number of continuous 0s, one for the number of continuous 1s, and the third to get the maximum among these two. Let's call them
**zeroes**,**ones**and**max**respectively. - Loop through str of length n, from 0 to n-1.
- If a '0' is encountered, increment
**zeroes**by 1, and decrement**ones**by 1. - Else if a '1' is encountered, increment
**ones**by 1, and decrement**zeroes**by 1. - If the value of
**zeroes**or**ones**goes below 0, reset it to 0 (since, there can not be less than 0 number of '0's or '1's). - Update
**max**in each iteration.

- If a '0' is encountered, increment
- Print
**max**.

Before taking a look at the code, let's apply the above approach on the first example.

## Example

```
Input: str = "1011"
Initial variables:
zeroes = 0
ones = 0
max = 0
Loop through the string,
Iteration 1
"1" encountered
ones = +1
zeroes = -1
Reset zeroes, zeroes = 0
max = 1
Iteration 2
"0" encountered
ones = 0
zeroes = +1
max = 1
Iteration 3
"1" encountered
ones = +1
zeroes = 0
max = 1
Iteration 4
"1" encontered
ones = +2
zeroes = -1
Reset zeroes, zeroes = 0
max = 2
End of loop,
max = 2 is the answer
which we have already confirmed.
```

Below is the implementation of the above approach in C++:

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str = "0100100111";
int n = str.length();
// variables to store continuous zeroes,
// continuous ones, and maximum among them.
int zeroes = 0, ones = 0, maxi = 0;
for (char c : str) {
// if 1 is found,
// increment ones and
// decrement zeroes.
if (c == '1') {
ones++, zeroes--;
}
// If 0 is found,
// increment zeroes and
// decrement ones.
else {
zeroes++, ones--;
}
// Update zeroes and ones
// to 0 if value goes below 0
zeroes = max(zeroes, 0);
ones = max(ones, 0);
// Update maximum value
maxi = max({ maxi, ones, zeroes });
}
cout << maxi;
}
```

### Output

```
3
```