Minimice los intercambios de caracteres del mismo índice para hacer la suma del valor ASCII de los caracteres de ambas strings impares

Dadas dos strings S y T de longitud N que consisten en alfabetos en minúsculas, la tarea es minimizar el número de intercambios de los mismos elementos indexados necesarios para que la suma del valor ASCII de los caracteres de ambas strings sea impar. Si no es posible hacer que la suma de los valores ASCII sea impar, imprima «-1» .

Ejemplos:

Entrada: S = ”acd”, T = ”dbf”
Salida: 1
Explicación:
Intercambiar S[1] y T[1] modifica S a “abd” y T a “dcf”.
Suma del valor ASCII de los caracteres de la string S = 97 + 98 + 100 = 297 ( Impar ).
Suma del valor ASCII de los caracteres de la string T = 100 + 99 + 102 = 301 ( Impar ).

Entrada: S = “aey”, T = “cgj”
Salida: -1

Enfoque: siga los pasos a continuación para resolver el problema:

• Calcula la suma de los valores ASCII de los caracteres de la string S y T y guárdala en las variables sum1 y sum2 respectivamente.
• Si sum1 y sum2 ya son impares, imprima 0 , ya que no se requieren intercambios.
• Si sum1 y sum2 tienen paridades diferentes, imprima -1 , ya que la suma no puede tener la misma paridad para ambas strings.
• Si sum1 y sum2 son pares , entonces recorre las strings S y T dadas . Si existe algún carácter con un valor ASCII impar , la suma de los valores ASCII de los caracteres de ambas strings puede hacerse impar con solo 1 intercambio. De lo contrario, imprima -1 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of swaps
// required to make the sum of ASCII values
// of the characters of both strings odd
void countSwaps(string S, string T)
{
    // Initialize alphabets with value
    int value[26];
 
    // Initialize values for each
    // alphabet
    for (int i = 0; i < 26; i++)
        value[i] = i + 1;
 
    // Size of the string
    int N = S.size();
 
    // Sum of string S
    int sum1 = 0;
 
    // Sum of string T
    int sum2 = 0;
 
    // Stores whether there is any
    // index i such that S[i] and
    // T[i] have different parities
    bool flag = false;
 
    // Traverse the strings
    for (int i = 0; i < N; i++) {
 
        // Update sum1 and sum2
        sum1 += value[S[i] - 'a'];
        sum2 += value[T[i] - 'a'];
 
        // If S[i] and T[i] have
        // different parities
        if ((value[S[i] - 'a'] % 2 == 0
             && value[T[i] - 'a'] % 2 == 1)
 
            || (value[S[i] - 'a'] % 2 == 1
                && value[T[i] - 'a'] % 2 == 0))
 
            flag = false;
    }
 
    // If sum1 and sum2 are both odd
    if (sum1 % 2 == 1
        && sum2 % 2 == 1)
        cout << "0\n";
 
    // If sum1 and sum2 are both even
    else if (sum1 % 2 == 0
             && sum2 % 2 == 0) {
 
        // If exists print 1
        if (flag)
            cout << "1";
 
        // Otherwise
        else
            cout << "-1";
    }
 
    // If sum1 and sum2 are
    // of different parities
    else {
        cout << "-1";
    }
}
 
// Driver Code
int main()
{
    string S = "acd";
    string T = "dbf";
 
    // Function Call
    countSwaps(S, T);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
 
  // Function to count the number of swaps
  // required to make the sum of ASCII values
  // of the characters of both strings odd
  static void countSwaps(String S, String T)
  {
 
    // Initialize alphabets with value
    int[] value = new int[26];
 
    // Initialize values for each
    // alphabet
    for (int i = 0; i < 26; i++)
      value[i] = i + 1;
 
    // Size of the string
    int N = S.length();
 
    // Sum of string S
    int sum1 = 0;
 
    // Sum of string T
    int sum2 = 0;
 
    // Stores whether there is any
    // index i such that S[i] and
    // T[i] have different parities
    boolean flag = false;
 
    // Traverse the strings
    for (int i = 0; i < N; i++) {
 
      // Update sum1 and sum2
      sum1 += value[S.charAt(i) - 'a'];
      sum2 += value[T.charAt(i) - 'a'];
 
      // If S[i] and T[i] have
      // different parities
      if ((value[S.charAt(i) - 'a'] % 2 == 0
           && value[T.charAt(i) - 'a'] % 2 == 1)
 
          || (value[S.charAt(i) - 'a'] % 2 == 1
              && value[T.charAt(i) - 'a'] % 2 == 0))
 
        flag = false;
    }
 
    // If sum1 and sum2 are both odd
    if (sum1 % 2 == 1
        && sum2 % 2 == 1)
      System.out.println("0\n");
 
    // If sum1 and sum2 are both even
    else if (sum1 % 2 == 0
             && sum2 % 2 == 0) {
 
      // If exists print 1
      if (flag)
        System.out.println("1");
 
      // Otherwise
      else
        System.out.println("-1");
    }
 
    // If sum1 and sum2 are
    // of different parities
    else {
      System.out.println("-1");
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    String S = "acd";
    String T = "dbf";
 
    // Function Call
    countSwaps(S, T);
  }
}
 
// This code is contributed by susmitakundugoaldanga.

# Python3 program for the above approach
 
# Function to count the number of swaps
# required to make the sum of ASCII values
# of the characters of both strings odd
def countSwaps(S, T):
   
    # Initialize alphabets with value
    value = [0]*26
 
    # Initialize values for each
    # alphabet
    for i in range(26):
        value[i] = i + 1
 
    # Size of the string
    N = len(S)
 
    # Sum of S
    sum1 = 0
 
    # Sum of T
    sum2 = 0
 
    # Stores whether there is any
    # index i such that S[i] and
    # T[i] have different parities
    flag = False
 
    # Traverse the strings
    for i in range(N):
 
        # Update sum1 and sum2
        sum1 += value[ord(S[i]) - ord('a')]
        sum2 += value[ord(T[i]) - ord('a')]
 
        # If ord(S[i]) anord('a)rd(T[i]) haord('a)
        # different parities
        if (value[ord(S[i]) - ord('a')] % 2 == 0
            and value[ord(T[i]) - ord('a')] % 2 == 1
            or value[ord(S[i]) - ord('a')] % 2 == 1
            and value[ord(T[i]) - ord('a')] % 2 == 0):
             
            flag = False
 
    # If sum1 and sum2 are both odd
    if (sum1 % 2 == 1 and sum2 % 2 == 1):
        print("0")
 
    # If sum1 and sum2 are both even
    elif (sum1 % 2 == 0 and sum2 % 2 == 0):
 
        # If exists pr1
        if (flag):
            print("1")
 
        # Otherwise
        else:
            print("-1")
 
    # If sum1 and sum2 are
    # of different parities
    else:
        print("-1")
 
# Driver Code
if __name__ == '__main__':
    S = "acd"
    T = "dbf"
 
    # Function Call
    countSwaps(S, T)
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
 
public class GFG
{
   
// Function to count the number of swaps
// required to make the sum of ASCII values
// of the characters of both strings odd
static void countSwaps(string S, string T)
{
   
    // Initialize alphabets with value
    int[] value = new int[26];
 
    // Initialize values for each
    // alphabet
    for (int i = 0; i < 26; i++)
        value[i] = i + 1;
 
    // Size of the string
    int N = S.Length;
 
    // Sum of string S
    int sum1 = 0;
 
    // Sum of string T
    int sum2 = 0;
 
    // Stores whether there is any
    // index i such that S[i] and
    // T[i] have different parities
    bool flag = false;
 
    // Traverse the strings
    for (int i = 0; i < N; i++) {
 
        // Update sum1 and sum2
        sum1 += value[S[i] - 'a'];
        sum2 += value[T[i] - 'a'];
 
        // If S[i] and T[i] have
        // different parities
        if ((value[S[i] - 'a'] % 2 == 0
             && value[T[i] - 'a'] % 2 == 1)
 
            || (value[S[i] - 'a'] % 2 == 1
                && value[T[i] - 'a'] % 2 == 0))
 
            flag = false;
    }
 
    // If sum1 and sum2 are both odd
    if (sum1 % 2 == 1
        && sum2 % 2 == 1)
        Console.Write("0\n");
 
    // If sum1 and sum2 are both even
    else if (sum1 % 2 == 0
             && sum2 % 2 == 0) {
 
        // If exists print 1
        if (flag)
            Console.Write("1");
 
        // Otherwise
        else
            Console.Write("-1");
    }
 
    // If sum1 and sum2 are
    // of different parities
    else {
        Console.Write("-1");
    }
}
 
 
// Driver Code
public static void Main(String[] args)
{
    string S = "acd";
    string T = "dbf";
 
    // Function Call
    countSwaps(S, T);
}
}
 
// This code is contributed by code_hunt.

<script>
      // JavaScript program for the above approach
 
      // Function to count the number of swaps
      // required to make the sum of ASCII values
      // of the characters of both strings odd
      function countSwaps(S, T)
      {
       
        // Initialize alphabets with value
        var value = [...Array(26)];
 
        // Initialize values for each
        // alphabet
        for (var i = 0; i < 26; i++) value[i] = i + 1;
 
        // Size of the string
        var N = S.length;
 
        // Sum of string S
        var sum1 = 0;
 
        // Sum of string T
        var sum2 = 0;
 
        // Stores whether there is any
        // index i such that S[i] and
        // T[i] have different parities
        var flag = false;
 
        // Traverse the strings
        for (var i = 0; i < N; i++) {
          // Update sum1 and sum2
          sum1 += value[S[i] - "a"];
          sum2 += value[T[i] - "a"];
 
          // If S[i] and T[i] have
          // different parities
          if (
            (value[S[i] - "a"] % 2 === 0 && value[T[i] - "a"] % 2 === 1) ||
            (value[S[i] - "a"] % 2 === 1 && value[T[i] - "a"] % 2 === 0)
          )
            flag = false;
        }
 
        // If sum1 and sum2 are both odd
        if (sum1 % 2 === 1 && sum2 % 2 === 1) document.write("0 <br>");
        // If sum1 and sum2 are both even
        else if (sum1 % 2 === 0 && sum2 % 2 === 0) {
          // If exists print 1
          if (flag) document.write("1");
          // Otherwise
          else document.write("-1");
        }
 
        // If sum1 and sum2 are
        // of different parities
        else {
          document.write("-1");
        }
      }
 
      // Driver Code
      var S = "aey";
      var T = "cgj";
       
      // Function Call
      countSwaps(S, T);
       
      // This code is contributed by rdtank.
    </script>

-1

Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo 
Espacio auxiliar: O(26), ya que estamos usando espacio adicional para la array de valores.