Reduce Hamming distance by swapping two characters
Given two strings S and T. Find the positions of two letters to be swapped in S so that the hamming distance between strings S and T is as small as possible.
Hamming Distance: Hamming distance between two strings S and T of the same length, which is defined as the number of positions in which S and T have different characters
Examples:
Input : S = "permanent", T = "pergament" Output: 4 6 Input : S = "double" T = "bundle" Output : 4 1
- Explanation 1: Initially, the hamming distance between S and T is 2(at 4 and 6). After swapping the letters at positions 4 and 6 it becomes “pernament”. Here, the hamming distance is only 1. This is the minimum possible.
- Explanation 2: Before swapping: “double” “bundle”, distance = 4
After swapping: “boudle” “bundle”, distance = 2
Approach :
In the given string, hamming distance can be decreased by at most two because, only two characters can be moved.
- Case-I: Decrease distance by two is possible, if there are two positions with the same two letters in two strings but that appear in different order(like “bundle” and “double”).
- Case-II: Decrease by one is possible by “fixing” the characters that are on wrong positions(like in “permanent” and “pergament”, here n stands in wrong pair with m and there is also unmatched m, which we can fix).
- Case-III: If not possible to decrease the hamming distance, print -1.
Implementation:
- Case-I: To decrease the distance by two, create a 2-d array dp[i][j](i is s[] – ‘a’ and j is t[] – ‘a’) and assign it to the index of i in string S. If repeated pair is found, print the corresponding indexes.
- Case-II: To decrease the distance by one, maintain two arrays A[] and B[]
Implementation:
C++
// C++ code to decrease // hamming distance using swap. #include <bits/stdc++.h> using namespace std; #define MAX 26 // Function to return the // swapped indexes to get // minimum hamming distance. void Swap(string s, string t, int n) { int dp[MAX][MAX]; memset (dp, -1, sizeof dp); // Find the initial hamming // distance int tot = 0; for ( int i = 0; i < n; i++) if (s[i] != t[i]) tot++; // Case-I: To decrease distance // by two for ( int i = 0; i < n; i++) { // ASCII values of present // character. int a = s[i] - 'a' ; int b = t[i] - 'a' ; if (a == b) continue ; // If two same letters appear // in different positions // print their indexes if (dp[a][b] != -1) { cout << i + 1 << " " << dp[a][b] + 1 << endl; return ; } // Store the index of // letters which is // in wrong position dp[b][a] = i; } // Case:II int A[MAX], B[MAX]; memset (A, -1, sizeof A); memset (B, -1, sizeof B); for ( int i = 0; i < n; i++) { int a = s[i] - 'a' ; int b = t[i] - 'a' ; if (a == b) continue ; // If misplaced letter // is found, print its // original index and // its new index if (A[b] != -1) { cout << i + 1 << " " << A[b] + 1 << endl; return ; } if (B[a] != -1) { cout << i + 1 << " " << B[a] + 1 << endl; return ; } // Store the index of // letters in wrong position A[a] = i; B[b] = i; } // Case-III cout << -1 << endl; } // Driver code int main() { string S = "permanent" ; string T = "pergament" ; int n = S.length(); if (S == "" || T == "" ) cout << "Required string is empty." ; else Swap(S, T, n); return 0; } |
Java
// Java code to decrease // hamming distance using swap. import java.util.Arrays; class GFG { static final int MAX = 26 ; // Function to return the // swapped indexes to get // minimum hamming distance. static void Swap(String s, String t, int n) { int dp[][] = new int [MAX][MAX]; for ( int i = 0 ; i < MAX; i++) { for ( int j = 0 ; j < MAX; j++) { dp[i][j]=- 1 ; } } // Find the initial hamming // distance int tot = 0 ; for ( int i = 0 ; i < n; i++) if (s.charAt(i) != t.charAt(i)) tot++; // Case-I: To decrease distance // by two for ( int i = 0 ; i < n; i++) { // ASCII values of present // character. int a = s.charAt(i)- 'a' ; int b = t.charAt(i) - 'a' ; if (a == b) continue ; // If two same letters appear // in different positions // print their indexes if (dp[a][b] != - 1 ) { System.out.println(i + 1 + " " + (dp[a][b] + 1 )); return ; } // Store the index of // letters which is // in wrong position dp[b][a] = i; } // Case:II int A[] = new int [MAX], B[] = new int [MAX]; Arrays.fill(A, - 1 ); Arrays.fill(B, - 1 ); for ( int i = 0 ; i < n; i++) { int a = s.charAt(i)- 'a' ; int b = t.charAt(i) - 'a' ; if (a == b) continue ; // If misplaced letter // is found, print its // original index and // its new index if (A[b] != - 1 ) { System.out.println(i + 1 + " " + (A[b] + 1 )); return ; } if (B[a] != - 1 ) { System.out.println(i + 1 + " " + (B[a] + 1 )); return ; } // Store the index of // letters in wrong position A[a] = i; B[b] = i; } // Case-III System.out.println(- 1 ); } // Driver code public static void main(String[] args) { String S = "permanent" ; String T = "pergament" ; int n = S.length(); if (S == "" || T == "" ) System.out.println( "Required string is empty." ); else Swap(S, T, n); } } // This code is contributed by Rajput-Ji |
Python 3
# Python 3 code to decrease # hamming distance using swap. MAX = 26 # Function to return the swapped indexes # to get minimum hamming distance. def Swap(s, t, n): dp = [[ - 1 for x in range ( MAX )] for y in range ( MAX )] # Find the initial hamming # distance tot = 0 ; for i in range (n): if (s[i] ! = t[i]): tot + = 1 # Case-I: To decrease distance # by two for i in range (n) : # ASCII values of present # character. a = ord (s[i]) - ord ( 'a' ) b = ord (t[i]) - ord ( 'a' ) if (a = = b): continue # If two same letters appear # in different positions # print their indexes if (dp[a][b] ! = - 1 ) : print (i + 1 , " " , dp[a][b] + 1 ) return # Store the index of # letters which is # in wrong position dp[b][a] = i # Case:II A = [ - 1 ] * MAX B = [ - 1 ] * MAX for i in range (n) : a = ord (s[i]) - ord ( 'a' ) b = ord (t[i]) - ord ( 'a' ) if (a = = b): continue # If misplaced letter is found, # print its original index and # its new index if (A[b] ! = - 1 ) : print ( i + 1 , A[b] + 1 ) return if (B[a] ! = - 1 ) : print ( i + 1 , B[a] + 1 ) return # Store the index of # letters in wrong position A[a] = i B[b] = i # Case-III print ( "-1" ) # Driver code if __name__ = = "__main__" : S = "permanent" T = "pergament" n = len (S) if (S = = " " or T == " "): print ( "Required string is empty." ) else : Swap(S, T, n) # This code is contributed # by ChitraNayal |
C#
// C# code to decrease // hamming distance using swap. using System; class GFG { static readonly int MAX = 26; // Function to return the // swapped indexes to get // minimum hamming distance. static void Swap( string s, string t, int n) { int [,]dp = new int [MAX, MAX]; for ( int i = 0; i < MAX; i++) { for ( int j = 0; j < MAX; j++) { dp[i, j]=-1; } } // Find the initial hamming // distance int tot = 0; for ( int i = 0; i < n; i++) if (s[i] != t[i]) tot++; // Case-I: To decrease distance // by two for ( int i = 0; i < n; i++) { // ASCII values of present // character. int a = s[i] - 'a' ; int b = t[i] - 'a' ; if (a == b) continue ; // If two same letters appear // in different positions // print their indexes if (dp[a,b] != -1) { Console.WriteLine(i + 1 + " " + (dp[a, b] + 1)); return ; } // Store the index of // letters which is // in wrong position dp[b,a] = i; } // Case:II int []A = new int [MAX]; int []B = new int [MAX]; for ( int i = 0; i < MAX; i++) { A[i]=-1; B[i]=-1; } for ( int i = 0; i < n; i++) { int a = s[i] - 'a' ; int b = t[i] - 'a' ; if (a == b) continue ; // If misplaced letter // is found, print its // original index and // its new index if (A[b] != -1) { Console.WriteLine(i + 1 + " " + (A[b] + 1)); return ; } if (B[a] != -1) { Console.WriteLine(i + 1 + " " + (B[a] + 1)); return ; } // Store the index of // letters in wrong position A[a] = i; B[b] = i; } // Case-III Console.WriteLine(-1); } // Driver code public static int Main() { string S = "permanent" ; string T = "pergament" ; int n = S.Length; if (S == "" || T == "" ) Console.WriteLine( "Required string is empty." ); else Swap(S, T, n); return 0; } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript code to decrease // hamming distance using swap. let MAX = 26; // Function to return the // swapped indexes to get // minimum hamming distance. function Swap(s,t,n) { let dp= new Array(MAX); for (let i = 0; i < MAX; i++) { dp[i]= new Array(MAX); for (let j = 0; j < MAX; j++) { dp[i][j]=-1; } } // Find the initial hamming // distance let tot = 0; for (let i = 0; i < n; i++) if (s[i] != t[i]) tot++; // Case-I: To decrease distance // by two for (let i = 0; i < n; i++) { // ASCII values of present // character. let a = s[i].charCodeAt(0)- 'a' .charCodeAt(0); let b = t[i].charCodeAt(0) - 'a' .charCodeAt(0); if (a == b) continue ; // If two same letters appear // in different positions // print their indexes if (dp[a][b] != -1) { document.write(i + 1 + " " + (dp[a][b] + 1)+ "<br>" ); return ; } // Store the index of // letters which is // in wrong position dp[b][a] = i; } // Case:II let A = new Array(MAX), B = new Array(MAX); for (let i=0;i<MAX;i++) { A[i]=-1; B[i]=-1; } for (let i = 0; i < n; i++) { let a = s[i].charCodeAt(0)- 'a' .charCodeAt(0); let b = t[i].charCodeAt(0) - 'a' .charCodeAt(0); if (a == b) continue ; // If misplaced letter // is found, print its // original index and // its new index if (A[b] != -1) { document.write(i + 1 + " " + (A[b] + 1)+ "<br>" ); return ; } if (B[a] != -1) { document.write(i + 1 + " " + (B[a] + 1)+ "<br>" ); return ; } // Store the index of // letters in wrong position A[a] = i; B[b] = i; } // Case-III document.write(-1); } // Driver code let S = "permanent" ; let T = "pergament" ; let n = S.length; if (S == "" || T == "" ) document.write( "Required string is empty." ); else Swap(S, T, n); // This code is contributed by avanitrachhadiya2155 </script> |
Output
6 4
Time Complexity: O(n), where n is the length of the given strings.
Auxiliary Space: O(MAX * MAX), where MAX is a predefined value. Here, MAX = 26
Contact Us