Introduction
Problem Statement
The problem states that we are given a binary string. We need to minimize the count of subsequences such that any subsequence doesn’t contain adjacent zeroes and ones and print the subsequence number corresponding to each element of the string.
A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
Adjacent Zeroes or ones means that the same element should not be consecutive. For example: “1001”, in this string two zeroes are consecutive, so 0’s are adjacent in this string.
Similarly “0110”, in this string two ones are consecutive, so 1’s are adjacent in this string.
Let’s discuss the sample test case. It will be more clear: :
Sample Examples
Example 1:
Input :
String S = ‘0011’, N = 4
Output:
2
1 2 1 2
Explanation:
The minimum number of subsequences required is 2.
Subsequence 1: ‘01.’
Subsequence 2: ‘01.’
The first Character of string S(‘0’) belongs to subsequence 1.
The second Character of string S(‘0’) belongs to subsequence 2.
The third Character of string S(‘1’) belongs to subsequence 1.
The fourth character string S(‘1’) belongs to subsequence 2.
It can be noted that, answers can also be [2,1,2,1], [2,1,1,2], [1,1,2,2], since there are many answers possible you can output any.
Example 2:
Input :
String S = ‘10110111’, N= 8
Output:
4
1 1 1 2 2 2 3 4
Therefore the minimum number of subsequences are 4.
Recommended topic about, kth largest element in an array, and Euclid GCD Algorithm
Solution Approach
The idea is to traverse the string, and if we find s[i] = ‘0’, we will check if we can add to any previous subsequence. If yes, we will add it, otherwise creating a new subsequence. Similarly, we will do this for s[i] = ‘1’. By doing this we can get minimum number of subsequences.
Now Let’s Look at the algorithms for doing this.
Steps of Algorithm
 Create an array ans to store the number of subsequences for each element of the string S.
 Create two vectors, endOne, and endZero; they will store the subsequence ending with ‘1’ and ‘0’, respectively.
 Traverse the string using the loop, and check if s[i] = ‘0’ or ‘1’. Also, declare a variable newSeq. It represents the new subsequence to be added if consecutive ‘0s’ or ‘1s’ are encountered.

If Character is 0, we will check if we can add to any previous subsequence:
 Check if endOne is empty or not. If it is empty, then we need to push newSeq into endZero.
 If endOne is not empty, then make newSeq equal to the last subsequence of endOne, now remove this sequence from endOne and add it to endZero as it is now ending with 0.

Similarly, if Character is 1, we will check if we can add to any previous subsequence:
 Check if endZero is empty or not. If it is empty, then we need to push newSeq into endOne.
 If endZero is not empty, then make newSeq equal to the last subsequence of endOne, now remove this sequence from endZero and add it to endOne as it is now ending with 1.
 Now, ans[i] = newSeq for every i.
 Repeat this process for the complete length of the string.
 The minimum number of subsequences is given by the sum of the length of endOne and endZero.
 Finally, output the ans array.