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 sumint 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 Codeint 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 sumdef 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 Codeif __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> |
Output
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
