Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Examples

Solution Approach

2.1.

Steps of Algorithm

Implementation in C++

3.1.

Complexity Analysis

Frequently asked questions

Key takeaways

Last Updated: Mar 27, 2024

Minimizing the count of a subsequence of a given binary string such that any subsequence doesn’t contain adjacent zeroes or ones

Q: Q1. What is the greedy approach?

Ans. It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.

Q: Q2. What is Dynamic Programming Approach?

Ans. Dynamic programming is an approach to optimize recursive solutions when recursive calls on the same input repeatedly. The idea is simple, store the result and need to calculate again and again to use it.

Q: Q3. What is prefix and suffix sum array?

Ans. Prefix Sum Array: Given an array of size N, let say arr[], then its prefixSum array is another array of size n, such that prefixSum[i] = arr[0] + arr[1] + arr[2] …. Arr[i].

Author Vaibhav Agarwal

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:
1. Check if endOne is empty or not. If it is empty, then we need to push newSeq into endZero.
2. 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:
1. Check if endZero is empty or not. If it is empty, then we need to push newSeq into endOne.
2. 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.

Implementation in C++

// c++ code for finding the minimum number of subsequences 
#include<bits/stdc++.h>
using namespace std;
// Function to find the minimum number of subsequences
// and to print each element belongs to which subsequence
void findSubsequence(string s, int n){
    // ans array to store subsequence number for each character
    int *ans = new int[n];
    // it will store subsequence ending with one or zero.
    vector<int>endOne, endZero;

    // traversing the whole string
    for(int i=0;i<n;i++){
        // if new subsequence is required
        int newSeq = endOne.size() + endZero.size();
        // if the current element is 1
        if(s[i] == '1'){
            // if there is subsequence ending with one
            if(endZero.size()>0){
                // update the new seq variable
                newSeq = endZero.back();
                // pop that subsequence as it will now end with one
                endZero.pop_back();
                // push into the endOne vector
                endOne.push_back(newSeq);
            }else{
                endOne.push_back(newSeq);
            }

        }else{
            // if there is subsequence ending with one
            if(endOne.size()>0){
                // update the newSeq variable
                newSeq = endOne.back();
                // pop that subsequence as it will now end with zero
                endOne.pop_back();
                // push into the endZero vector
                endZero.push_back(newSeq);
            }else{
                endZero.push_back(newSeq);
            }
        }
        ans[i] = newSeq;
    }
    // printing minimum number of subsequences 
    cout << endOne.size() + endZero.size() << endl;
    // subsequence number for each element of the string 
    for(int i=0;i<n;i++){
        cout << ans[i] + 1 << " ";
    }
}
int main(){
    string s;
    s = "10110111";
    int n = 8;
    // calling the findSubsequence function
    findSubsequence(s, n);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

4
1 1 1 2 2 2 3 4

Complexity Analysis

Time Complexity: O(N)

Explanation: Since we are traversing the string linearly only for finding the minimum number of subsequences, therefore Time complexity is O(N).

Space Complexity: O(N)

Explanation: We are making endOne and endZero vector, which will be O(N) in worst case. Therefore time complexity is O(N).

Also check out - Substr C++

Frequently asked questions

Q1. What is the greedy approach?

Ans. It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.

Q2. What is Dynamic Programming Approach?

Ans. Dynamic programming is an approach to optimize recursive solutions when recursive calls on the same input repeatedly. The idea is simple, store the result and need to calculate again and again to use it.

Q3. What is prefix and suffix sum array?

Ans. Prefix Sum Array: Given an array of size N, let say arr[], then its prefixSum array is another array of size n, such that prefixSum[i] = arr[0] + arr[1] + arr[2] …. Arr[i].

Suffix Sum Array: Given an array of size N, let say arr[], then its suffixSum array is another array of size n, such that suffixSum[i] = arr[i] + arr[i+1] + arr[i+2] …. Arr[n].

Key takeaways

In this article, we have discussed the problem of finding the minimum number of subsequences of a given binary string such that any subsequence doesn’t contain adjacent zeroes or ones and print the subsequence number to which each element of given string belongs to. We hope you understand the problem and solution properly. Now you can do more similar questions.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!