Minimum steps to determine the subsequence with max 1s based on given conditions
Given a string S of size N consisting of β0β, β1β and β?β, where N is always even. Divide the string into two different strings say S1 and S2, where S1 will only contain the characters at even indices of S and S2 will only contain the characters at odd indices of S. The task is to find the minimum possible steps required to predict which one of the two strings S1 and S2 will have the maximum count of 1βs. In one step, choose one character for either S1 or S2. If the character is β0β then pick β0β, if the character is β1β then pick β1β and if the character is β?β then choose any one of β1β or β0β.
Example:
Input: s = β?10?0?β
Output: 4
Explanation:
Step 1: For S1 character to choose is S[0]=β?β, so choose β0β. S1=β0β³, S2=ββ.
Step 2: For S2 character to choose is S[1]=β1β², so choose β1β. S1=β0β³, S2=β1β³.
Step 1: For S1 character to choose is S[2]=β?β, so choose β0β. S1=β00β³, S2=β1β³.
Step 1: For S1 character to choose is S[3]=β?β, so choose β1β. S1=β00β³, S2=β11β³.
After Step 4, S2 will have more number of 1βs irrespective of what number is chosen for the remaining indexes.Input: s = β?1?0??0110β
Output: 7
Approach: The idea is to solve the problem recursively, and to answer this after exploring all possible outcomes. Now, to solve this problem, follow the below steps:
- Create a function named minSteps having parameters, string S, a pointer i which will point to the current location in the string until which the string is divided, integers count1 and count2 which will store the number of ones till i in S1 and S2 respectively, integers first and second to store the available places in S1 and S2 for which no value is chosen, and an integer n which denotes the size of the string S. This function will return the minimum steps required to predict the answer.
- Now initially, the current pointer is at zero so i=0. Since no values are chosen for S1 and S2 till now and all places in S1 and S2 are available to fill, so count1=0, count2=0, first = n/2 and second=n/2. So, now make a call to the function minSteps with these arguments.
- In each call of the function minSteps:
- Check for the base cases, that are:
- If i reaches n (i.e. i=n) because this means that both S1 and S2 are fully filled, and now the answer can definitely be predicted. So, return 0.
- If count1 becomes greater than the sum of second and count2 then return 0, because now, even after selecting all ones for available places in S2, S1 will have more number of ones.
- If count2 becomes greater than the sum of first and count1 then return 0, because of the reason stated above.
- After checking for base cases, check if i is even or odd. If i is even then this index is being chosen by S1 otherwise S2.
- So, decrement first or second based on what string is currently being filled, because the available places in that string will reduce by one place after filling.
- Now if the current character is β?β (i.e. s[i] = β?β) then make both recursive calls of choosing β1β and of choosing β0β, and return the minimum out of the two after adding 1 to them.
- Otherwise, make a single call and return the answer after adding one to that.
- Check for the base cases, that are:
- The last recursive call will give the answer to this question.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; //// Recursive function to minimum steps // required after combining two strings int minSteps(string& S, int i, int count1, int count2, int first, int second, int n) { // If current pointer reaches the end if (i == n) { return 0; } // Condition to conclude that one string does // more ones than the other irrespective of what // number is chosen for the remaining indexes if (count1 > (second + count2) || count2 > (first + count1)) { return 0; } int c1 = 0, c2 = 0; // If i is even, then choosing character for S1 if (i % 2 == 0) { if (S[i] == '?' ) { return min( 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n), 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n)); } else if (S[i] == '1' ) { c1 = 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n); return c1; } else { c2 = 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n); return c2; } } // If i is odd else { if (S[i] == '?' ) { return min( 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n), 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n)); } else if (S[i] == '1' ) { c1 = 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n); return c1; } else { c2 = 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n); return c2; } } } // Driver Code int main() { string s = "?10?0?" ; int N = s.size(); cout << minSteps(s, 0, 0, 0, N / 2, N / 2, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { //// Recursive function to minimum steps // required after combining two strings static int minSteps(String S, int i, int count1, int count2, int first, int second, int n) { // If current pointer reaches the end if (i == n) { return 0 ; } // Condition to conclude that one string does // more ones than the other irrespective of what // number is chosen for the remaining indexes if (count1 > (second + count2) || count2 > (first + count1)) { return 0 ; } int c1 = 0 , c2 = 0 ; // If i is even, then choosing character for S1 if (i % 2 == 0 ) { if (S.charAt(i) == '?' ) { return Math.min( 1 + minSteps( S, i + 1 , count1 + 1 , count2, first - 1 , second, n), 1 + minSteps( S, i + 1 , count1, count2, first - 1 , second, n)); } else if (S.charAt(i) == '1' ) { c1 = 1 + minSteps( S, i + 1 , count1 + 1 , count2, first - 1 , second, n); return c1; } else { c2 = 1 + minSteps( S, i + 1 , count1, count2, first - 1 , second, n); return c2; } } // If i is odd else { if (S.charAt(i) == '?' ) { return Math. min( 1 + minSteps( S, i + 1 , count1, count2 + 1 , first, second - 1 , n), 1 + minSteps( S, i + 1 , count1, count2, first, second - 1 , n)); } else if (S.charAt(i) == '1' ) { c1 = 1 + minSteps( S, i + 1 , count1, count2 + 1 , first, second - 1 , n); return c1; } else { c2 = 1 + minSteps( S, i + 1 , count1, count2, first, second - 1 , n); return c2; } } } // Driver code public static void main (String[] args) { String s = "?10?0?" ; int N = s.length(); System.out.println(minSteps(s, 0 , 0 , 0 , N / 2 , N / 2 , N)); } } // This code is contributed by sanjoy_62. |
Python3
# Python code for the above approach import math # Recursive function to minimum steps # required after combining two strings def minSteps(S, i, count1, count2, first, second, n): # If current pointer reaches the end if i = = n: return 0 # Condition to conclude that one string does # more ones than the other irrespective of what # number is chosen for the remaining indexes if count1 > second + count2 or count2 > first + count1: return 0 c1 = 0 c2 = 0 # If i is even, then choosing character for S1 if i % 2 = = 0 : if S[i] = = '?' : return min ( 1 + minSteps( S, i + 1 , count1 + 1 , count2, first - 1 , second, n), 1 + minSteps( S, i + 1 , count1, count2, first - 1 , second, n)) elif S[i] = = '1' : c1 = 1 + minSteps( S, i + 1 , count1 + 1 , count2, first - 1 , second, n) return c1 else : c2 = 1 + minSteps( S, i + 1 , count1, count2, first - 1 , second, n) return c2 # If i is odd else : if S[i] = = '?' : return min ( 1 + minSteps( S, i + 1 , count1, count2 + 1 , first, second - 1 , n), 1 + minSteps( S, i + 1 , count1, count2, first, second - 1 , n)) elif S[i] = = '1' : c1 = 1 + minSteps( S, i + 1 , count1, count2 + 1 , first, second - 1 , n) return c1 else : c2 = 1 + minSteps( S, i + 1 , count1, count2, first, second - 1 , n) return c2 # Driver Code s = "?10?0?" N = len (s) print (minSteps(s, 0 , 0 , 0 , math.floor(N / 2 ), math.floor(N / 2 ), N)) # This code is contributed by Potta Lokesh |
C#
// C# program for the above approach using System; class GFG { //// Recursive function to minimum steps // required after combining two strings static int minSteps( string S, int i, int count1, int count2, int first, int second, int n) { // If current pointer reaches the end if (i == n) { return 0; } // Condition to conclude that one string does // more ones than the other irrespective of what // number is chosen for the remaining indexes if (count1 > (second + count2) || count2 > (first + count1)) { return 0; } int c1 = 0, c2 = 0; // If i is even, then choosing character for S1 if (i % 2 == 0) { if (S[i] == '?' ) { return Math.Min( 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n), 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n)); } else if (S[i] == '1' ) { c1 = 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n); return c1; } else { c2 = 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n); return c2; } } // If i is odd else { if (S[i] == '?' ) { return Math.Min( 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n), 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n)); } else if (S[i] == '1' ) { c1 = 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n); return c1; } else { c2 = 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n); return c2; } } } // Driver code public static void Main () { string s = "?10?0?" ; int N = s.Length; Console.Write(minSteps(s, 0, 0, 0, N / 2, N / 2, N)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach //// Recursive function to minimum steps // required after combining two strings function minSteps(S, i, count1, count2, first, second, n) { // If current pointer reaches the end if (i == n) { return 0; } // Condition to conclude that one string does // more ones than the other irrespective of what // number is chosen for the remaining indexes if (count1 > (second + count2) || count2 > (first + count1)) { return 0; } let c1 = 0, c2 = 0; // If i is even, then choosing character for S1 if (i % 2 == 0) { if (S[i] == '?' ) { return Math.min( 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n), 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n)); } else if (S[i] == '1' ) { c1 = 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n); return c1; } else { c2 = 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n); return c2; } } // If i is odd else { if (S[i] == '?' ) { return Math.min( 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n), 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n)); } else if (S[i] == '1' ) { c1 = 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n); return c1; } else { c2 = 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n); return c2; } } } // Driver Code let s = "?10?0?" ; let N = s.length; document.write(minSteps(s, 0, 0, 0, N / 2, N / 2, N)); // This code is contributed by Samim Hossain Mondal. </script> |
4
Time Complexity: O(2^N)
Auxiliary Space: O(1)
Contact Us