Maximize sum by splitting given binary strings based on given conditions
Given two binary strings str1 and str2 each of length N, the task is to split the strings in such a way that the sum is maximum with given conditions.
- Split both strings at the same position into equal length substrings.
- If both the substrings have only 0βs then the value of that substring to be added is 1.
- If both the substrings have only 1βs then the value of that substring to be added is 0.
- If both the substrings have 0βs and 1βs then the value of that substring to be added is 2.
Return the maximum sum possible.
Examples:
Input: str1 = β0101000β, str2 = β1101100β
Output: 8
Explanation:
Split like this:
Take β0β from str1 and β1β from str2 -> 2
Take β10β from str1 and β10β from str2 -> 2
Take β1β from str1 and β1β from str2 -> 0
Take β0β from str1 and β1β from str2 -> 2
Take β0β from str1 and β0β from str2 -> 1
Take β0β from str1 and β0β from str2 -> 1
Sum is 2 + 2 + 0 + 2 + 1 + 1 => 8Input: str1 = β01β, str2 = β01β
Output: 2
Approach: This problem can be solved using the greedy approach. First, take some of the distinct pair means (0, 1) because it gives the maximum value 2 or with a distinct value pair with the same value pair, the maximum value is 2 so there is no benefit. then try to make pair of (0, 0) with (1, 1) or vice versa to maximize the sum.
- Initialize the MaxSum to 0.
- Traverse the strings. If Ai is not equal to Bi, increment the MaxSum by 2.
- Traverse the strings again and try to pair with opposite value means 0 with 1 or 1 with 0.
- Check previous and next value of string if itβs opposite increment MaxSum by 2.
- Else if the pair is only (0, 0) increment MaxSum by 1.
Below is the implementation of the above-mentioned approach:
C++
// C++ program to split two // binary strings in such a way // such that sum is maximum. #include <iostream> using namespace std; // Function to split strings // to find maximum sum int MaxSum(string a, string b) { int ans = 0; for ( int i = 0; i < a.length(); i++) { if (a[i] != b[i]) ans += 2; } int n = a.length(); // Traverse the strings. for ( int i = 0; i < n; i++) { if (a[i] == b[i]) { if (a[i] == '0' ) { // If Ai is not equal to Bi, // increment the MaxSum by 2 if (i + 1 < n and a[i + 1] == '1' and b[i + 1] == '1' ) { ans += 2, i++; } // Else if the pair is only (0, 0) // increment MaxSum by 1. else { ans += 1; } } else { if (i + 1 < n and a[i + 1] == '0' and b[i + 1] == '0' ) { ans += 2, i++; } else { ans += 0; } } } } return ans; } // Driver Code int main() { string a = "0101000" ; string b = "1101100" ; cout << MaxSum(a, b); return 0; } |
Java
// Java program to split two // binary Strings in such a way // such that sum is maximum. import java.io.*; public class GFG { // Function to split Strings // to find maximum sum static int MaxSum(String a, String b) { int ans = 0 ; for ( int i = 0 ; i < a.length(); i++) { if (a.charAt(i) != b.charAt(i)) ans += 2 ; } int n = a.length(); // Traverse the Strings. for ( int i = 0 ; i < n; i++) { if (a.charAt(i) == b.charAt(i)) { if (a.charAt(i) == '0' ) { // If Ai is not equal to Bi, // increment the MaxSum by 2 if (i + 1 < n && a.charAt(i + 1 ) == '1' && b.charAt(i + 1 ) == '1' ) { ans += 2 ; i++; } // Else if the pair is only (0, 0) // increment MaxSum by 1. else { ans += 1 ; } } else { if (i + 1 < n && a.charAt(i + 1 ) == '0' && b.charAt(i + 1 ) == '0' ) { ans += 2 ; i++; } else { ans += 0 ; } } } } return ans; } // Driver Code public static void main(String args[]) { String a = "0101000" ; String b = "1101100" ; System.out.println(MaxSum(a, b)); } } // This code is contributed by Saurabh Jaiswal |
Python3
# python3 program to split two # binary strings in such a way # such that sum is maximum. # Function to split strings # to find maximum sum def MaxSum(a, b): ans = 0 for i in range ( 0 , len (a)): if (a[i] ! = b[i]): ans + = 2 n = len (a) # Traverse the strings. i = 0 while i < n: if (a[i] = = b[i]): if (a[i] = = '0' ): # If Ai is not equal to Bi, # increment the MaxSum by 2 if (i + 1 < n and a[i + 1 ] = = '1' and b[i + 1 ] = = '1' ): ans, i = ans + 2 , i + 1 # Else if the pair is only (0, 0) # increment MaxSum by 1. else : ans + = 1 else : if (i + 1 < n and a[i + 1 ] = = '0' and b[i + 1 ] = = '0' ): ans, i = ans + 2 , i + 1 else : ans + = 0 i + = 1 return ans # Driver Code if __name__ = = "__main__" : a = "0101000" b = "1101100" print (MaxSum(a, b)) # This code is contributed by rakeshsahni |
C#
// C# program to split two // binary strings in such a way // such that sum is maximum. using System; class GFG { // Function to split strings // to find maximum sum static int MaxSum( string a, string b) { int ans = 0; for ( int i = 0; i < a.Length; i++) { if (a[i] != b[i]) ans += 2; } int n = a.Length; // Traverse the strings. for ( int i = 0; i < n; i++) { if (a[i] == b[i]) { if (a[i] == '0' ) { // If Ai is not equal to Bi, // increment the MaxSum by 2 if (i + 1 < n && a[i + 1] == '1' && b[i + 1] == '1' ) { ans += 2; i++; } // Else if the pair is only (0, 0) // increment MaxSum by 1. else { ans += 1; } } else { if (i + 1 < n && a[i + 1] == '0' && b[i + 1] == '0' ) { ans += 2; i++; } else { ans += 0; } } } } return ans; } // Driver Code public static void Main() { string a = "0101000" ; string b = "1101100" ; Console.Write(MaxSum(a, b)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to split strings // to find maximum sum function MaxSum(a, b) { let ans = 0; for (let i = 0; i < a.length; i++) { if (a[i] != b[i]) ans += 2; } let n = a.length; // Traverse the strings. for (let i = 0; i < n; i++) { if (a[i] == b[i]) { if (a[i] == '0' ) { // If Ai is not equal to Bi, // increment the MaxSum by 2 if (i + 1 < n && a[i + 1] == '1' && b[i + 1] == '1' ) { ans += 2, i++; } // Else if the pair is only (0, 0) // increment MaxSum by 1. else { ans += 1; } } else { if (i + 1 < n && a[i + 1] == '0' && b[i + 1] == '0' ) { ans += 2, i++; } else { ans += 0; } } } } return ans; } // Driver Code let a = "0101000" ; let b = "1101100" ; document.write(MaxSum(a, b)); // This code is contributed by Potta Lokesh </script> |
8
Time Complexity: O(N)
Auxiliary Space: O(1)