Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Solution Approach
2.1.
Steps of Algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently asked questions
5.
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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

  1. Create an array ans to store the number of subsequences for each element of the string S. 
  2. Create two vectors, endOne, and endZero; they will store the subsequence ending with ‘1’ and ‘0’, respectively. 
  3. 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. 
  4. 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.
  5. 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. 
  6. Now, ans[i] = newSeq for every i. 
  7. Repeat this process for the complete length of the string. 
  8. The minimum number of subsequences is given by the sum of the length of endOne and endZero. 
  9. Finally, output the ans array. 
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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! 

Recommended Problems:

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Previous article
Maximize the Confusion of an Exam
Next article
Count of All Substrings in a Binary String in Which Count of 1’s is Strictly More than the Count of 0’s
Live masterclass