Given two strings A and B of equal lengths consisting of lower case English letters. The task is to count the minimum number of pre-processing moves on string A required to make it equal to string B after applying below operations:
- Choose any index i (0 ? i < n) and swap characters ai and bi.
- Choose any index i (0 ? i < n) and swap characters ai and an – i – 1.
- Choose any index i (0 ? i < n) and swap characters bi and bn – i – 1.
In one pre-process move you can replace a character in A with any other character of English alphabet.
Examples:
Input: A = “abacaba”, B = “bacabaa”
Output: 4
Preprocess moves are as follows:
Set A0 = ‘b’, A2 = ‘c’, A3 = ‘a’ and A4 = ‘b’ and A becomes “bbcabba”.
Then we can obtain equal strings by the following sequence of operations:
swap(A1, B1) and swap(A1, A5).Input: A = “zcabd” B = “dbacz”
Output: 0
No preprocess moves are required.
We can use the following sequence of changes to make A and B equal:
swap(B0, B4) then swap(A1, A3).
Approach: Let’s divide all characters of both strings into groups in such a way that characters in each group can be swapped with each other with changes. So, there will be following groups: {A0, An – 1, B0, Bn – 1}, {A1, An – 2, B1, Bn – 2} and so on. Since these groups don’t affect each other, we can calculate the number of pre-processing moves in each group and then sum it up.
How to determine if a group does not need any pre-processing moves?
For a group consisting of 2 characters (there will be one such group if n is odd) that’s easy – If the characters in this group are equal, the answer is 0, otherwise, it’s 1.
To determine the required number of pre-processing moves for a group consisting of four characters, we may use the following fact: this group doesn’t require any pre-processing moves if the characters in this group can be divided into pairs. So if the group contains four equal characters or two pairs of equal characters, then the answer for this group is 0. Otherwise, we may check that replacing only one character of Ai and An – i – 1 will be enough. If so, then the answer is 1, otherwise, it’s 2.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum number of // pre-processing moves required on string A int Preprocess(string A, string B) { // Length of the given strings int n = A.size(); // To store the required answer int ans = 0; // Run a loop upto n/2 for (int i = 0; i < n / 2; i++) { // To store frequency of 4 characters map<char, int> mp; mp[A[i]]++; mp[A[n - i - 1]]++; mp[B[i]]++; mp[B[n - i - 1]]++; int sz = mp.size(); // If size is 4 if (sz == 4) ans += 2; // If size is 3 else if (sz == 3) ans += 1 + (A[i] == A[n - i - 1]); // If size is 2 else if (sz == 2) ans += mp[A[i]] != 2; } // If n is odd if (n % 2 == 1 && A[n / 2] != B[n / 2]) ans++; return ans; } // Driver code int main() { string A = "abacaba", B = "bacabaa"; cout << Preprocess(A, B); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the minimum number of // pre-processing moves required on string A static int Preprocess(String A, String B) { // Length of the given strings int n = A.length(); // To store the required answer int ans = 0; // Run a loop upto n/2 for (int i = 0; i < n / 2; i++) { // To store frequency of 4 characters HashMap<Character, Integer> mp = new HashMap<>(); if(mp.containsKey(A.charAt(i))) mp.put(A.charAt(i), mp.get(A.charAt(i))+1); else mp.put(A.charAt(i), 1); if(mp.containsKey(A.charAt(n-i-1))) mp.put(A.charAt(n-i-1), mp.get(A.charAt(n-i-1))+1); else mp.put(A.charAt(n-i-1), 1); if(mp.containsKey(B.charAt(i))) mp.put(B.charAt(i), mp.get(B.charAt(i))+1); else mp.put(B.charAt(i), 1); if(mp.containsKey(B.charAt(n-i-1))) mp.put(B.charAt(n-i-1), mp.get(B.charAt(n-i-1))+1); else mp.put(B.charAt(n-i-1), 1); int sz = mp.size(); // If size is 4 if (sz == 4) ans += 2; // If size is 3 else if (sz == 3) ans += 1 + (A.charAt(i) == A.charAt(n - i - 1) ? 1 : 0 ); // If size is 2 else if (sz == 2) ans += mp.get(A.charAt(i)) != 2 ? 1 : 0; } // If n is odd if (n % 2 == 1 && A.charAt(n / 2) != B.charAt(n / 2)) ans++; return ans; } // Driver code public static void main (String[] args) { String A = "abacaba", B = "bacabaa"; System.out.println(Preprocess(A, B)); } } // This code is contributed by ihritik |
Python3
# Python3 implementation of the approach # Function to return the minimum number of # pre-processing moves required on string A def Preprocess(A, B): # Length of the given strings n = len(A) # To store the required answer ans = 0 # Run a loop upto n/2 for i in range(n // 2): # To store frequency of 4 characters mp = dict() mp[A[i]] = 1 if A[i] == A[n - i - 1]: mp[A[n - i - 1]] += 1 if B[i] in mp.keys(): mp[B[i]] += 1 else: mp[B[i]] = 1 if B[n - i - 1] in mp.keys(): mp[B[n - 1 - i]] += 1 else: mp[B[n - 1 - i]] = 1 sz = len(mp) # If size is 4 if (sz == 4): ans += 2 # If size is 3 elif (sz == 3): ans += 1 + (A[i] == A[n - i - 1]) # If size is 2 elif (sz == 2): ans += mp[A[i]] != 2 # If n is odd if (n % 2 == 1 and A[n // 2] != B[n // 2]): ans += 1 return ans # Driver code A = "abacaba"B = "bacabaa"print(Preprocess(A, B)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the minimum number of // pre-processing moves required on string A static int Preprocess(string A, string B) { // Length of the given strings int n = A.Length; // To store the required answer int ans = 0; // Run a loop upto n/2 for (int i = 0; i < n / 2; i++) { // To store frequency of 4 characters Dictionary<char, int> mp = new Dictionary<char, int>(); if(mp.ContainsKey(A[i])) mp[A[i]]++; else mp[A[i]] = 1; if(mp.ContainsKey(A[n-i-1])) mp[A[n - i - 1]]++; else mp[A[n - i - 1]] = 1; if(mp.ContainsKey(B[i])) mp[B[i]]++; else mp[B[i]] = 1; if(mp.ContainsKey(B[n-i-1])) mp[B[n - i - 1]]++; else mp[B[n - i - 1]] = 1; int sz = mp.Count; // If size is 4 if (sz == 4) ans += 2; // If size is 3 else if (sz == 3) ans += 1 + (A[i] == A[n - i - 1] ? 1 : 0 ); // If size is 2 else if (sz == 2) ans += mp[A[i]] != 2 ? 1 : 0; } // If n is odd if (n % 2 == 1 && A[n / 2] != B[n / 2]) ans++; return ans; } // Driver code public static void Main () { string A = "abacaba", B = "bacabaa"; Console.WriteLine(Preprocess(A, B)); } } // This code is contributed by ihritik |
PHP
<?php // PHP implementation of the approach // Function to return the minimum number of // pre-processing moves required on string A function Preprocess($A, $B) { // Length of the given strings $n = strlen($A); // To store the required answer $ans = 0; // To store frequency of 4 characters $mp = array(); for($i = 0; $i < $n ; $i++) $mp[$A[$i]] = 0; // Run a loop upto n/2 for ($i = 0; $i < floor($n / 2); $i++) { $mp[$A[$i]]++; $mp[$A[$n - $i - 1]]++; $mp[$B[$i]]++; $mp[$B[$n - $i - 1]]++; $sz = sizeof($mp); // If size is 4 if ($sz == 4) $ans += 2; // If size is 3 else if ($sz == 3) if($A[$i] == $A[$n - $i - 1]) $ans += 1; else $ans += 1; // If size is 2 else if ($sz == 2) $ans += $mp[$A[$i]] != 2; } // If n is odd if ($n % 2 == 1 && ($A[floor($n / 2)] != $B[floor($n / 2)])) $ans++; return $ans; } // Driver code $A = "abacaba"; $B = "bacabaa"; echo Preprocess($A, $B); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the minimum number of // pre-processing moves required on string A function Preprocess(A, B) { // Length of the given strings let n = A.length; // To store the required answer let ans = 0; // Run a loop upto n/2 for(let i = 0; i < n / 2; i++) { // To store frequency of 4 characters let mp = new Map(); if (mp.has(A[i])) mp.set(A[i], mp.get(A[i]) + 1); else mp.set(A[i], 1); if (mp.has(A[n - i - 1])) mp.set(A[n - i - 1], mp.get(A[n - i - 1]) + 1); else mp.set(A[n - i - 1], 1); if (mp.has(B[i])) mp.set(B[i], mp.get(B[i]) + 1); else mp.set(B[i], 1); if (mp.has(B[n - i - 1])) mp.set(B[n - i - 1], mp.get(B[n - i - 1]) + 1); else mp.set(B[n - i - 1], 1); let sz = mp.size; // If size is 4 if (sz == 4) ans += 2; // If size is 3 else if (sz == 3) ans += 1 + (A[i] == A[n - i - 1] ? 1 : 0); // If size is 2 else if (sz == 2) ans += mp.get(A[i]) != 2 ? 1 : 0; } // If n is odd if (n % 2 == 1 && A[(Math.floor(n / 2))] != B[(Math.floor(n / 2))]) ans++; return ans; } // Driver code let A = "abacaba", B = "bacabaa"; document.write(Preprocess(A, B)); // This code is contributed by unknown2108 </script> |
4
Time complexity: O(N) where N is the length of strings
Auxiliary space: O(1) because it is using constant extra space
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
