Wednesday, 27 Oct 2021

# Minimize swaps of same-indexed characters to make sum of ASCII value of characters of both the strings odd

Minimize swaps of same-indexed characters to make sum of ASCII value of characters of both the strings odd
Given two N-length strings S and T consisting of lowercase alphabets, the task is to minimize the number of swaps of same indexed elements required to make the sum of ASCII value of characters of both the strings odd. If it is not possible to make the sum of ASCII values odd, then print “-1”.
Examples:

Input:S = ”acd”, T = ”dbf”Output: 1Explanation:Swapping S and T modifies S to “abd” and T to “dcf”.Sum of ASCII value of characters of the string S = 97 + 98 + 100 = 297 (Odd).Sum of ASCII value of characters of the string T = 100 + 99 + 102 = 301 (Odd).
Input: S = “aey”, T = “cgj”Output: -1

Approach: Follow the steps below to solve the problem:
Calculate the sum of ASCII values of the characters of the string S and T and store it in variables sum1 and sum2 respectively.
If sum1 and sum2 are already odd, then print 0, as no swaps are required.
If sum1 and sum2 are of different parities, print -1, as the sum cannot be of same parity for both the strings.
If sum1 and sum2 are both even, then traverse the given strings S and T. If there exists any character with odd ASCII value, sum of ASCII values of the characters of both the strings can be made odd by only 1 swap. Otherwise, print -1.
Below is the implementation of the above approach:

C++

#include
using namespace std;

void countSwaps(string S, string T)
{

int value;

for (int i = 0; i < 26; i++)         value[i] = i + 1;             int N = S.size();             int sum1 = 0;             int sum2 = 0;                       bool flag = false;             for (int i = 0; i < N; i++) {                     sum1 += value[S[i] - 'a'];         sum2 += value[T[i] - 'a'];                              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 % 2 == 1         && sum2 % 2 == 1)         cout