Maximice la suma dividiendo strings binarias dadas según las condiciones dadas

Dadas dos strings binarias str1 y str2 cada una de longitud N, la tarea es dividir las strings de tal manera que la suma sea máxima con las condiciones dadas.

• Divida ambas strings en la misma posición en substrings de igual longitud.
• Si ambas substrings tienen solo 0, entonces el valor de esa substring que se agregará es 1.
• Si ambas substrings tienen solo 1, entonces el valor de esa substring que se agregará es 0.
• Si ambas substrings tienen 0 y 1, entonces el valor de esa substring que se agregará es 2.

Devolver la suma máxima posible.

Ejemplos: 

Entrada: str1 = “0101000”, str2 = “1101100”
Salida: 8
Explicación:
Dividir así:
Tomar “0” de str1 y “1” de str2 -> 2
Tomar “10” de str1 y “10” de str2 – > 2
Tomar “1” de str1 y “1” de str2 -> 0
Tomar “0” de str1 y “1” de str2 -> 2
Tomar “0” de str1 y “0” de str2 -> 1
Tomar “0” ” de str1 y “0” de str2 -> 1 La
suma es 2 + 2 + 0 + 2 + 1 + 1 => 8

Entrada: str1 = “01”, str2 = “01”
Salida: 2

Enfoque : este problema se puede resolver utilizando el enfoque codicioso. Primero, tome algunos de los medios de pares distintos (0, 1) porque da el valor máximo 2 o con un par de valores distintos con el mismo par de valores, el valor máximo es 2, por lo que no hay beneficio. luego intente hacer un par de (0, 0) con (1, 1) o viceversa para maximizar la suma.

• Inicialice MaxSum a 0.
• Atraviesa las cuerdas. Si Ai no es igual a Bi, incremente MaxSum en 2.
• Atraviese las cuerdas nuevamente e intente emparejar con valor opuesto significa 0 con 1 o 1 con 0.
• Verifique el valor anterior y siguiente de la string si es opuesto, incremente MaxSum en 2.
• De lo contrario, si el par es solo (0, 0), incremente MaxSum en 1.

A continuación se muestra la implementación del enfoque mencionado anteriormente:

// 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 program to split two
// binary Strings in such a way
// such that sum is maximum.
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 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# 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.

<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

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)