Check if one string can be made another by swapping at most once

Problem

Given two strings A and B, check if A can be made equal to B by swapping two characters of A at most once.

Sample Input

"aba"
"aab"

Sample Output

True

Explanation

Swap index 1 with index 2 to get “aab”

Approach

We use two indices, can1 and can2 , to store up to two different positions between strings A and B. If there are/is:

• More than two different locations that are not the same, the answer is False.
• Two different characters, compare A[can1] vs B[can2] and A[can2] vs B[can1].
• Only one distinct location, return False.
• No difference between A and B. See if A has at least one duplicate letter so that we can swap them.

Complexity Analysis

The time complexity is O(N), and the space complexity is O(26)

C++ Programming

#include <bits/stdc++.h>
using namespace std;

// function to check if one string can be made equal to another
bool solve(string A, string B) {

        // if size of strings is not same, return False
        if (A.size() != B.size()) return false;

        int can1 = -1, can2 = -1;

        unordered_set<char> SetA;

        for (int i = 0; i < A.size(); i++) {
            if (A[i] != B[i]) {
                if (can1 == -1)
                    can1 = i;

                else if (can2 == -1)
                    can2 = i;

                else
                    return false; // More than 2 different places between A & B
            }
            SetA.insert(A[i]);
        }

        if (can1 != -1 && can2 != -1) // If there are 2 different places
            return A[can1] == B[can2] && A[can2] == B[can1]; 

        if (can1 != -1) // Only have 1 different place
            return false;

        return SetA.size() < A.size(); // No difference between A & B, check if A contains at least 1 duplicate letter.
    }

int main() {
    string A = "aba";
    string B = "aab";
    if(solve(A, B))
    {
        cout<<"True";
    }
    else
    {
        cout<<"False";
    }
}

Output

True

Java Programming

import java.io.*;
import java.util.*;  
class Solution {

    // function to check if one string can be made equal to another
    public static boolean solve(String A, String B) {
        
        // if size of strings is not same, return False
        if (A.length() != B.length()) return false;
        int can1 = -1, can2 = -1;
        Set<Character> SetA = new HashSet<>();

        for (int i = 0; i < A.length(); i++) {
            if (A.charAt(i) != B.charAt(i)) {
                if (can1 == -1)
                    can1 = i;
                else if (can2 == -1)
                    can2 = i;
                else
                    return false; // More than 2 different places between A & B
            }
            SetA.add(A.charAt(i));
        }

        if (can1 != -1 && can2 != -1) // There are 2 different places
            return A.charAt(can1) == B.charAt(can2) && A.charAt(can2) == B.charAt(can1);

        if (can1 != -1) // Only have 1 different place
            return false;

        return SetA.size() < A.length(); // If there is no difference between A & B, check if A contains at least 1 duplicate letters.
    }

    public static void main (String[] args) {
        String A = "aba";
        String B = "aab";

        System.out.println(solve(A, B));
    }
}

Output

true

Python Programming

# function to check if one string can be made equal to another
def solve(A, B):
    # if size of strings is not same, return False
    if len(A) != len(B): return False
    can1, can2 = -1, -1
    SetA = set()

    for i in range(len(A)):
        if A[i] != B[i]:
            if can1 == -1:
                can1 = i
            elif can2 == -1:
                can2 = i
            else:
                return False # More than 2 different places between A & B
        SetA.add(A[i])

    if can1 != -1 and can2 != -1: # if there are 2 different places
        return A[can1] == B[can2] and A[can2] == B[can1]

    if can1 != -1: # Only have 1 different place
        return False

    return len(SetA) < len(A) # No difference between A & B, check if A contains at least 1 duplicate letter

A = "aba"
B = "aab"
print(solve(A, B))

Output

True

People are also reading:

• Delete Nodes And Return Forest
• Modular Exponentiation in Logarithmic Time
• Find MSB in O(1)
• Longest Substring without repeating characters
• Count subarrays with given XOR
• Nth root of M
• Find MSB
• Check if directed graph is connected
• Find dropping point of an egg
• Find all symmetric pairs in an array of pairs