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

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

1. 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.
2. 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.
3. 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

Time Complexity: O(n)