Given a binary string S consisting of ‘0‘ and ‘1‘ only, the task is to find the maximum possible number of “10” subsequences by replacing at most one 0 with 1.
Examples:
Input: 1110
Output: 3
Explanation: Here initial answer = 3, since pairs: {0, 3}, {1, 3} and {2, 3} initially form the given subsequence. So no need to perform any operations since after performing operation answer would decrease. Hence answer is 3Input: 101100
Output: 8
Explanation: Here initial answer = 7, since pairs {0, 1}, {0, 4}, {0, 5}, {2, 4}, {2, 5}, {3, 5} and {3, 4} formed the subsequence. If we perform operation on index 1 we get new string as 111100 which gives 8 possible subsequence.
Approach: To solve the problem follow the below idea :
Since it’s allowed to convert a value from ‘0’ to ‘1’, we can think greedily to get our answer.
If we change one ‘0’ to ‘1’, It results in the addition of extra subsequences formed due to changing of ‘0’ to ‘1’. However, it also leads to a loss in a certain amount of subsequences that ‘0’ was initially forming with its previous ‘1’s. Hence we need to select a position such that greedily Net profit = gain(from extra good pairs generated) – loss (originally good pairs destroyed) is maximized.
So how do we calculate it efficiently:
For this purpose, we need to create a suffix array that stores the number of ‘0’ to its right in the string so that we can find the profit after converting that ‘0’ to ‘1’. Also, we need to create a prefix array that stores the number of ‘1’ to its left such that we can find loss after converting that ‘0’ to ‘1’.
Follow the steps to solve the problem:
- Create an array of size N + 1 for storing how many zeros appear after a character.
- Check the last char first, then for the remaining chars by using a loop running from (i = n – 2 to 0).
- Again, do the same thing for storing the appearance of ones in the prefix of any character.
- Calculate the initial answer by adding 0s in the suffix for all indices.
- Run a loop from i = 0 to N:
- Calculate the maximum profit among all the indices.
- Add the initial answer and maximum profit, which is our final answer, and return that value.
Below is the implementation of the approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// good pairs that satisfy the conditionsint maximum_subseq(string s){ int n = s.length(); // To store how many zero appear // in front of that to form good pair vector<int> number_of_zero_suffix(n + 1); // Checking if its value is 0 number_of_zero_suffix[n - 1] = (s[n - 1] == '0'); for (int i = n - 2; i >= 0; i--) { number_of_zero_suffix[i] = number_of_zero_suffix[i + 1] + (s[i] == '0'); } // Prefix array to count the number of // '1' which appear before to it which // would decrease the number of good pairs vector<int> number_of_one_prefix(n); number_of_one_prefix[0] = (s[0] == '1'); for (int i = 1; i < n; i++) { number_of_one_prefix[i] = number_of_one_prefix[i - 1] + (s[i] == '1'); } int initial_answer = 0; for (int i = 0; i < n; i++) { if (s[i] == '1') // Counting initial answer in // the original string initial_answer += number_of_zero_suffix[i + 1]; } int maxi = 0; int profit = 0, loss = 0; for (int i = 0; i < n; i++) { if (s[i] == '0') { if (i == n - 1) profit = 0; else profit = number_of_zero_suffix[i + 1]; if (i == 0) loss = 0; else loss = number_of_one_prefix[i - 1]; // Calculating net profit int net = profit - loss; // Storing maximum value of net // profit after performing // the operation. maxi = max(maxi, net); } } // Calculating final answer. int answer = initial_answer + maxi; return answer;}// Driver codeint main(){ // First test case string S1 = "1110"; cout << maximum_subseq(S1) << "\n"; // Second test case string S2 = "10110"; cout << maximum_subseq(S2) << "\n"; // Third test case string S3 = "101100"; cout << maximum_subseq(S3) << "\n"; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to count the number of // good pairs that satisfy the conditions static int maximum_subseq(String s) { int n = s.length(); // To store how many zero appear // in front of that to form good pair int[] number_of_zero_suffix = new int[n + 1]; // Checking if its value is 0 number_of_zero_suffix[n - 1] = ((s.charAt(n - 1) == '0') ? 1 : 0); for (int i = n - 2; i >= 0; i--) { number_of_zero_suffix[i] = number_of_zero_suffix[i + 1] + ((s.charAt(i) == '0') ? 1 : 0); } // Prefix array to count the number of // '1' which appear before to it which // would decrease the number of good pairs int[] number_of_one_prefix = new int[n]; number_of_one_prefix[0] = (s.charAt(0) == '1' ? 1 : 0); for (int i = 1; i < n; i++) { number_of_one_prefix[i] = number_of_one_prefix[i - 1] + ((s.charAt(i) == '1' ? 1 : 0)); } int initial_answer = 0; for (int i = 0; i < n; i++) { if (s.charAt(i) == '1') { // Counting initial answer in // the original string initial_answer += number_of_zero_suffix[i + 1]; } } int maxi = 0; int profit = 0, loss = 0; for (int i = 0; i < n; i++) { if (s.charAt(i) == '0') { if (i == n - 1) { profit = 0; } else { profit = number_of_zero_suffix[i + 1]; } if (i == 0) { loss = 0; } else { loss = number_of_one_prefix[i - 1]; } // Calculating net profit int net = profit - loss; // Storing maximum value of net // profit after performing // the operation. maxi = Math.max(maxi, net); } } // Calculating final answer. int answer = initial_answer + maxi; return answer; } public static void main(String[] args) { // First test case String S1 = "1110"; System.out.println(maximum_subseq(S1)); // Second test case String S2 = "10110"; System.out.println(maximum_subseq(S2)); // Third test case String S3 = "101100"; System.out.println(maximum_subseq(S3)); }}// This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach# Function to count the number of# good pairs that satisfy the conditionsdef maximum_subseq(s): n = len(s) # To store how many zero appear # in front of that to form good pair number_of_zero_suffix = [] for i in range(0,n+1): number_of_zero_suffix.append(0) # Checking if its value is 0 number_of_zero_suffix[n - 1] = (s[n - 1] == '0') for i in range(n-2,-1,-1): number_of_zero_suffix[i] = number_of_zero_suffix[i + 1] + (s[i] == '0') # Prefix array to count the number of # '1' which appear before to it which # would decrease the number of good pairs number_of_one_prefix = [] for i in range(0,n): number_of_one_prefix.append(0) number_of_one_prefix[0] = (s[0] == '1') for i in range(1,n): number_of_one_prefix[i] = number_of_one_prefix[i - 1] + (s[i] == '1') initial_answer = 0 for i in range(0,n): if (s[i] == '1'): #Counting initial answer in #the original string initial_answer += number_of_zero_suffix[i + 1] maxi = 0 profit = 0 loss = 0 for i in range(0,n): if (s[i] == '0'): if (i == n - 1): profit = 0 else: profit = number_of_zero_suffix[i + 1] if (i == 0): loss = 0 else: loss = number_of_one_prefix[i - 1] # Calculating net profit net = profit - loss # Storing maximum value of net # profit after performing # the operation. maxi = max(maxi, net) # Calculating final answer. answer = initial_answer + maxi return answer# Driver code# First test caseS1 = "1110"print(maximum_subseq(S1))# Second test caseS2 = "10110"print(maximum_subseq(S2))# Third test caseS3 = "101100"print(maximum_subseq(S3))# This code is contributed by akashish__ |
C#
// C# implementationusing System;public class GFG { // Function to count the number of // good pairs that satisfy the conditions public static int maximum_subseq(string s) { int n = s.Length; // To store how many zero appear // in front of that to form good pair int[] number_of_zero_suffix = new int[n + 1]; // Checking if its value is 0 if (s[n - 1] == '0') { number_of_zero_suffix[n - 1] = 1; } else number_of_zero_suffix[n - 1] = 0; for (int i = n - 2; i >= 0; i--) { if (s[i] == '0') { number_of_zero_suffix[i] = number_of_zero_suffix[i + 1] + 1; } else { number_of_zero_suffix[i] = number_of_zero_suffix[i + 1] + 0; } } // Prefix array to count the number of // '1' which appear before to it which // would decrease the number of good pairs int[] number_of_one_prefix = new int[n]; if (s[0] == '1') number_of_one_prefix[0] = 1; else number_of_one_prefix[0] = 0; for (int i = 1; i < n; i++) { if (s[i] == '1') { number_of_one_prefix[i] = number_of_one_prefix[i - 1] + 1; } else { number_of_one_prefix[i] = number_of_one_prefix[i - 1] + 0; } } int initial_answer = 0; for (int i = 0; i < n; i++) { if (s[i] == '1') // Counting initial answer in // the original string initial_answer += number_of_zero_suffix[i + 1]; } int maxi = 0; int profit = 0, loss = 0; for (int i = 0; i < n; i++) { if (s[i] == '0') { if (i == n - 1) profit = 0; else profit = number_of_zero_suffix[i + 1]; if (i == 0) loss = 0; else loss = number_of_one_prefix[i - 1]; // Calculating net profit int net = profit - loss; // Storing maximum value of net // profit after performing // the operation. maxi = Math.Max(maxi, net); } } // Calculating final answer. int answer = initial_answer + maxi; return answer; } static public void Main() { // First test case string S1 = "1110"; Console.WriteLine(maximum_subseq(S1)); // Second test case string S2 = "10110"; Console.WriteLine(maximum_subseq(S2)); // Third test case string S3 = "101100"; Console.WriteLine(maximum_subseq(S3)); }}// This code is contributed by ksam24000 |
Javascript
// Function to count the number of// good pairs that satisfy the conditionsfunction maximum_subseq(s){ let n = s.length; // To store how many zero appear // in front of that to form good pair let number_of_zero_suffix = []; for(let i=0;i<(n + 1);i++) { number_of_zero_suffix.push(0); } // Checking if its value is 0 number_of_zero_suffix[n - 1] = (s[n - 1] == '0'); for (let i = n - 2; i >= 0; i--) { number_of_zero_suffix[i] = number_of_zero_suffix[i + 1] + (s[i] == '0'); } // Prefix array to count the number of // '1' which appear before to it which // would decrease the number of good pairs let number_of_one_prefix = []; for(let i=0;i<n;i++) { number_of_one_prefix.push(0); }; number_of_one_prefix[0] = (s[0] == '1'); for (let i = 1; i < n; i++) { number_of_one_prefix[i] = number_of_one_prefix[i - 1] + (s[i] == '1'); } let initial_answer = 0; for (let i = 0; i < n; i++) { if (s[i] == '1') // Counting initial answer in // the original string initial_answer += number_of_zero_suffix[i + 1]; } let maxi = 0; let profit = 0, loss = 0; for (let i = 0; i < n; i++) { if (s[i] == '0') { if (i == n - 1) profit = 0; else profit = number_of_zero_suffix[i + 1]; if (i == 0) loss = 0; else loss = number_of_one_prefix[i - 1]; // Calculating net profit let net = profit - loss; // Storing maximum value of net // profit after performing // the operation. maxi = Math.max(maxi, net); } } // Calculating final answer. let answer = initial_answer + maxi; return answer;}// Driver code// First test caselet S1 = "1110";console.log(maximum_subseq(S1));// Second test caselet S2 = "10110";console.log(maximum_subseq(S2));// Third test caselet S3 = "101100";console.log(maximum_subseq(S3));// This code is contributed by akashish__ |
Output
3 4 8
Time complexity: O(N),
Auxiliary Space: O(N)
Related Articles:
Take a part in the ongoing discussion
