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

Posted in

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

Vinay Khatri
Last updated on June 29, 2022

    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 more than two different locations that are not the same, the answer is False. If there are two different characters, compare A[can1] vs B[can2] and A[can2] vs B[can1]. If there is only one distinct location, return False. If there is 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:

    Leave a Comment on this Post

    0 Comments