Reduce Hamming distance by swapping two characters

Namachila November 18, 2025

0 0 8 minutes read

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

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!