Split a Binary String such that count of 0s and 1s in left and right substrings is maximum
Given a binary string, str of length N, the task is to find the maximum sum of the count of 0s on the left substring and count of 1s on the right substring possible by splitting the binary string into two non-empty substrings.
Examples:
Input: str = “000111”
Output: 6
Explanation:
Splitting the binary string into “000” and “111”.
Count of 0s in the left substring of the string = 3
Count of 1s in the right substring of the string = 3
Therefore, the sum of the count of 0s in the left substring of the string and the count of 1s in the right substring of the string = 3 + 3 = 6.
Input: S = “1111”
Output: 3
Explanation:
Splitting the binary string into “1” and “111”.
Count of 0s in the left substring of the string = 0
Count of 1s in the right substring of the string = 3
Therefore, the sum of the count of 0s in the left substring of the string and the count of 1s in the right substring of the string = 0 + 3 = 3.
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say res, to store the maximum sum of count of 0s in left substring and count of 1s in the right substring.
- Initialize a variable, say cntOne, to store count of 1s in the given binary string.
- Traverse the binary string and for each character, check if it is ‘1’ or not. If found to be true, then increment the value of cntOne by 1.
- Initialize two variables, say zero and one, to store the count of 0s and count of 1s till ith index.
- Traverse the binary string and update the value of res = max(res, cntOne – one + zero).
- Finally, print the value of res.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum sum of count of // 0s in the left substring and count of 1s in // the right substring by splitting the string int maxSumbySplittingstring(string str, int N) { // Stores count of 1s // the in binary string int cntOne = 0; // Traverse the binary string for ( int i = 0; i < N; i++) { // If current character is '1' if (str[i] == '1' ) { // Update cntOne cntOne++; } } // Stores count of 0s int zero = 0; // Stores count of 1s int one = 0; // Stores maximum sum of count of // 0s and 1s by splitting the string int res = 0; // Traverse the binary string for ( int i = 0; i < N - 1; i++) { // If current character // is '0' if (str[i] == '0' ) { // Update zero zero++; } // If current character is '1' else { // Update one one++; } // Update res res = max(res, zero + cntOne - one); } return res; } // Driver Code int main() { string str = "00111" ; int N = str.length(); cout << maxSumbySplittingstring(str, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to find the maximum sum of count of // 0s in the left subString and count of 1s in // the right subString by splitting the String static int maxSumbySplittingString(String str, int N) { // Stores count of 1s // the in binary String int cntOne = 0 ; // Traverse the binary String for ( int i = 0 ; i < N; i++) { // If current character is '1' if (str.charAt(i) == '1' ) { // Update cntOne cntOne++; } } // Stores count of 0s int zero = 0 ; // Stores count of 1s int one = 0 ; // Stores maximum sum of count of // 0s and 1s by splitting the String int res = 0 ; // Traverse the binary String for ( int i = 0 ; i < N - 1 ; i++) { // If current character // is '0' if (str.charAt(i) == '0' ) { // Update zero zero++; } // If current character is '1' else { // Update one one++; } // Update res res = Math.max(res, zero + cntOne - one); } return res; } // Driver Code public static void main(String[] args) { String str = "00111" ; int N = str.length(); System.out.print(maxSumbySplittingString(str, N)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement # the above approach # Function to find the maximum sum of count of # 0s in the left suband count of 1s in # the right subby splitting the string def maxSumbySplittingstring( str , N): # Stores count of 1s # the in binary string cntOne = 0 # Traverse the binary string for i in range (N): # If current character is '1' if ( str [i] = = '1' ): # Update cntOne cntOne + = 1 # Stores count of 0s zero = 0 # Stores count of 1s one = 0 # Stores maximum sum of count of # 0s and 1s by splitting the string res = 0 # Traverse the binary string for i in range (N - 1 ): # If current character # is '0' if ( str [i] = = '0' ): # Update zero zero + = 1 # If current character is '1' else : # Update one one + = 1 # Update res res = max (res, zero + cntOne - one) return res # Driver Code if __name__ = = '__main__' : str = "00111" N = len ( str ) print (maxSumbySplittingstring( str , N)) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement // the above approach using System; public class GFG { // Function to find the maximum sum of count of // 0s in the left subString and count of 1s in // the right subString by splitting the String static int maxSumbySplittingString(String str, int N) { // Stores count of 1s // the in binary String int cntOne = 0; // Traverse the binary String for ( int i = 0; i < N; i++) { // If current character is '1' if (str[i] == '1' ) { // Update cntOne cntOne++; } } // Stores count of 0s int zero = 0; // Stores count of 1s int one = 0; // Stores maximum sum of count of // 0s and 1s by splitting the String int res = 0; // Traverse the binary String for ( int i = 0; i < N - 1; i++) { // If current character // is '0' if (str[i] == '0' ) { // Update zero zero++; } // If current character is '1' else { // Update one one++; } // Update res res = Math.Max(res, zero + cntOne - one); } return res; } // Driver Code public static void Main(String[] args) { String str = "00111" ; int N = str.Length; Console.Write(maxSumbySplittingString(str, N)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the maximum sum of count of // 0s in the left substring and count of 1s in // the right substring by splitting the string function maxSumbySplittingstring(str, N) { // Stores count of 1s // the in binary string var cntOne = 0; // Traverse the binary string for ( var i = 0; i < N; i++) { // If current character is '1' if (str[i] == '1' ) { // Update cntOne cntOne++; } } // Stores count of 0s var zero = 0; // Stores count of 1s var one = 0; // Stores maximum sum of count of // 0s and 1s by splitting the string var res = 0; // Traverse the binary string for ( var i = 0; i < N - 1; i++) { // If current character // is '0' if (str[i] == '0' ) { // Update zero zero++; } // If current character is '1' else { // Update one one++; } // Update res res = Math.max(res, zero + cntOne - one); } return res; } // Driver Code var str = "00111" ; var N = str.length; document.write( maxSumbySplittingstring(str, N)); </script> |
5
Time complexity: O(N)
Auxiliary Space: O(1)
Contact Us