Minimize count of alternating subsequences to divide given Binary String with subsequence number
Given a binary string S of length N. The task is to find the following:
- The minimum number of subsequences, string S can be divided into, such that the subsequence does not contain adjacent zeroes or ones.
- Subsequence number to which each character of string S belongs.
If there are many answers, output any.
Examples:
Input: S = β0011β, N = 4
Output:
2
1 2 2 1
Explanation:
There can be a minimum of 2 subsequences such that they donot have any adjacent zeroes or ones.
Subsequence 1: β01β
Subsequence 2: β01β
Also, the first character of S(β0β) belongs to subsequence 1(β01β)
Second character of S(β0β) belongs to subsequence 2(β01β)
Third character of S(β1β) belongs to subsequence 2(β01β)
Fourth character of S(β1β) belongs to subsequence 1(β01β)Input: S = β1000110β, N = 7
Output:
3
1 1 2 3 3 2 2
Approach: It is to be noted that 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. Now, follow the steps below to solve the problem:
- Create a vector ans to store the subsequences to which each character of string S belongs.
- Also, create two vectors endZero and endOne to store the subsequences ending with β0β and β1β respectively.
- As there canβt be adjacent zeroes or ones in a subsequence. Hence, if a character is β0β, the next character to be put in the subsequence must be β1β and vice versa.
- Now, using a loop traverse over each character of S and check if it is β0β or β1β. Also, declare a variable newSeq which represents the new subsequence to be formed if consecutive zeroes or ones are encountered.
- If a character is β0β, check whether the vector endOne is empty or not:
- If it is empty, then push newSeq into endZero.
- Otherwise, put the last subsequence of endOne into newSeq. Now, this last subsequence of endOne does not end with β1β anymore as β0β has been appended to it. Thus, push it in endZero.
- Similarly, if a character in S is β1β, the same steps as above are followed, i.e., check whether vector endZero is empty or not:
- If it is empty, then push newSeq into endOne.
- Otherwise, put the last subsequence of endZero into newSeq. Now, this last subsequence of endZero does not end with β0β anymore as β1β has been appended to it. Thus, push it in endOne.
- Then, push newSeq into vector ans.
- Repeat the above steps for each character of S.
- The minimum number of subsequences will be given by the sum of the sizes of endZero and endOne.
- Finally, output the minimum number of subsequences and the vector ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number of // subsequences into which S has to divide // and the subsequences to which each character // of S belongs to. void findSeq(string S, int N) { // Stores the subsequences to which each // character of S belongs to. vector< int > ans(N); // Store the subsequences ending with zeroes // and ones respectively. vector< int > endZero, endOne; // Loop to traverse each character of S for ( int i = 0; i < N; ++i) { // Stores the number of new // subsequence to be formed int newSeq = endZero.size() + endOne.size(); // If the character is '0' if (S[i] == '0' ) { // If there is no string // which ends with '1' if (endOne.empty()) { // Push newSeq into endZero endZero.push_back(newSeq); } else { // Put the last element // of endOne into newSeq newSeq = endOne.back(); // Remove the last // element of endOne endOne.pop_back(); // newSeq ends with '0' endZero.push_back(newSeq); } } else { // If there is no string // which ends with '0' if (endZero.empty()) { // Push newSeq into endOne endOne.push_back(newSeq); } else { // Put the last element // of endZero into newSeq newSeq = endZero.back(); // Remove the last element of endOne endZero.pop_back(); // newSeq ends with '1' endOne.push_back(newSeq); } } // Put newSeq into vector ans ans[i] = newSeq; } // Output the minimum // number of subsequences cout << endZero.size() + endOne.size() << endl; // Output the subsequences // to which each character // of S belongs to for ( int i = 0; i < N; ++i) { // Add 1 as the index starts from 0 cout << ans[i] + 1 << " " ; } } // Driver Code int main() { // Given input string S = "1000110" ; int N = 7; // Function Call findSeq(S, N); return 0; } |
Java
// Java program for the above approach import java.util.ArrayList; class GFG { // Function to find the minimum number of // subsequences into which S has to divide // and the subsequences to which each character // of S belongs to. public static void findSeq(String S, int N) { // Stores the subsequences to which each // character of S belongs to. int [] ans = new int [N]; // Store the subsequences ending with zeroes // and ones respectively. ArrayList<Integer> endZero = new ArrayList<Integer>(); ArrayList<Integer> endOne = new ArrayList<Integer>(); // Loop to traverse each character of S for ( int i = 0 ; i < N; ++i) { // Stores the number of new // subsequence to be formed int newSeq = endZero.size() + endOne.size(); // If the character is '0' if (S.charAt(i) == '0' ) { // If there is no string // which ends with '1' if (endOne.isEmpty()) { // Push newSeq into endZero endZero.add(newSeq); } else { // Put the last element // of endOne into newSeq newSeq = endOne.get(endOne.size() - 1 ); // Remove the last // element of endOne endOne.remove(endOne.size() - 1 ); // newSeq ends with '0' endZero.add(newSeq); } } else { // If there is no string // which ends with '0' if (endZero.isEmpty()) { // Push newSeq into endOne endOne.add(newSeq); } else { // Put the last element // of endZero into newSeq newSeq = endZero.get(endZero.size() - 1 ); // Remove the last element of endOne endZero.remove(endZero.size() - 1 ); // newSeq ends with '1' endOne.add(newSeq); } } // Put newSeq into vector ans ans[i] = newSeq; } // Output the minimum // number of subsequences System.out.println(endZero.size() + endOne.size()); // Output the subsequences // to which each character // of S belongs to for ( int i = 0 ; i < N; ++i) { // Add 1 as the index starts from 0 System.out.print(ans[i] + 1 + " " ); } } // Driver Code public static void main(String args[]) { // Given input String S = "1000110" ; int N = 7 ; // Function Call findSeq(S, N); } } // This code is contributed by gfgking. |
Python3
# python program for the above approach # Function to find the minimum number of # subsequences into which S has to divide # and the subsequences to which each character # of S belongs to. def findSeq(S, N): # Stores the subsequences to which each # character of S belongs to. ans = [ 0 for _ in range (N)] # Store the subsequences ending with zeroes # and ones respectively. endZero = [] endOne = [] # Loop to traverse each character of S for i in range ( 0 , N): # Stores the number of new # subsequence to be formed newSeq = len (endZero) + len (endOne) # If the character is '0' if (S[i] = = '0' ): # If there is no string # which ends with '1' if ( len (endOne) = = 0 ): # Push newSeq into endZero endZero.append(newSeq) else : # Put the last element # of endOne into newSeq newSeq = endOne[ len (endOne) - 1 ] # Remove the last # element of endOne endOne.pop() # newSeq ends with '0' endZero.append(newSeq) else : # If there is no string # which ends with '0' if ( len (endZero) = = 0 ): # Push newSeq into endOne endOne.append(newSeq) else : # Put the last element # of endZero into newSeq newSeq = endZero[ len (endZero) - 1 ] # Remove the last element of endOne endZero.pop() # newSeq ends with '1' endOne.append(newSeq) # Put newSeq into vector ans ans[i] = newSeq # Output the minimum # number of subsequences print ( len (endZero) + len (endOne)) # Output the subsequences # to which each character # of S belongs to for i in range ( 0 , N): # Add 1 as the index starts from 0 print (ans[i] + 1 , end = " " ) # Driver Code if __name__ = = "__main__" : # Given input S = "1000110" N = 7 # Function Call findSeq(S, N) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the minimum number of // subsequences into which S has to divide // and the subsequences to which each character // of S belongs to. public static void findSeq(String S, int N) { // Stores the subsequences to which each // character of S belongs to. int [] ans = new int [N]; // Store the subsequences ending with zeroes // and ones respectively. List< int > endZero = new List< int >(); List< int > endOne = new List< int >(); // Loop to traverse each character of S for ( int i = 0; i < N; ++i) { // Stores the number of new // subsequence to be formed int newSeq = endZero.Count + endOne.Count; // If the character is '0' if (S[i] == '0' ) { // If there is no string // which ends with '1' if (endOne.Count == 0) { // Push newSeq into endZero endZero.Add(newSeq); } else { // Put the last element // of endOne into newSeq newSeq = endOne[endOne.Count - 1]; // Remove the last // element of endOne endOne.Remove(endOne.Count - 1); // newSeq ends with '0' endZero.Add(newSeq); } } else { // If there is no string // which ends with '0' if (endZero.Count == 0) { // Push newSeq into endOne endOne.Add(newSeq); } else { // Put the last element // of endZero into newSeq newSeq = endZero[endZero.Count - 1]; // Remove the last element of endOne endZero.Remove(endZero.Count - 1); // newSeq ends with '1' endOne.Add(newSeq); } } // Put newSeq into vector ans ans[i] = newSeq; } // Output the minimum // number of subsequences Console.WriteLine(endZero.Count + endOne.Count); // Output the subsequences // to which each character // of S belongs to for ( int i = 0; i < N; ++i) { // Add 1 as the index starts from 0 Console.Write(ans[i] + 1 + " " ); } } // Driver Code public static void Main() { // Given input String S = "1000110" ; int N = 7; // Function Call findSeq(S, N); } } // This code is contributed by gfgking. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum number of // subsequences into which S has to divide // and the subsequences to which each character // of S belongs to. function findSeq(S, N) { // Stores the subsequences to which each // character of S belongs to. let ans = new Array(N); // Store the subsequences ending with zeroes // and ones respectively. let endZero = [], endOne = []; // Loop to traverse each character of S for (let i = 0; i < N; ++i) { // Stores the number of new // subsequence to be formed let newSeq = endZero.length + endOne.length; // If the character is '0' if (S[i] == '0' ) { // If there is no string // which ends with '1' if (endOne.length == 0) { // Push newSeq into endZero endZero.push(newSeq); } else { // Put the last element // of endOne into newSeq newSeq = endOne[endOne.length - 1]; // Remove the last // element of endOne endOne.pop(); // newSeq ends with '0' endZero.push(newSeq); } } else { // If there is no string // which ends with '0' if (endZero.length == 0) { // Push newSeq into endOne endOne.push(newSeq); } else { // Put the last element // of endZero into newSeq newSeq = endZero[endZero.length - 1]; // Remove the last element of endOne endZero.pop(); // newSeq ends with '1' endOne.push(newSeq); } } // Put newSeq into vector ans ans[i] = newSeq; } // Output the minimum // number of subsequences document.write(endZero.length + endOne.length + '<br>' ); // Output the subsequences // to which each character // of S belongs to for (let i = 0; i < N; ++i) { // Add 1 as the index starts from 0 document.write(ans[i] + 1 + " " ); } } // Driver Code // Given input let S = "1000110" ; let N = 7; // Function Call findSeq(S, N); // This code is contributed by Potta Lokesh </script> |
3 1 1 2 3 3 2 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us