One Away
You are given two strings, string A and string B. Your task is to determine whether string A can be transformed into string B by performing only one of the following operations at most one (or maybe zero) time.

1. You can delete a character from any position. 2. You can replace a character with any other character. 3. You can insert a character at any position.

Note :

1. The strings are non-empty. 2. The strings only contain lowercase English letters.

Input Format :

The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains a string A. The second line of each test case contains a string B.

Output Format :

For each test case print in a new line, “True” if string A can be transformed into string B or “False” if this can’t be done.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

One Away

You are given two strings, string A and string B. Your task is to determine whether string A can be transformed into string B by performing only one of the following operations at most one (or maybe zero) time.

1. You can delete a character from any position.
2. You can replace a character with any other character.
3. You can insert a character at any position.

Note :

1. The strings are non-empty.
2. The strings only contain lowercase English letters.

Input Format :

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains a string A. 

The second line of each test case contains a string B.

Output Format :

For each test case print in a new line, “True” if string A can be transformed into string B or “False” if this can’t be done.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= |A| <= 10^4
1 <= |B| <= 10^4

Where where |A| represents the size of the string A and where |B| represents the size of the string B.

Time Limit: 1sec

Accepted Answer

The idea is to create a new character array and copy the characters from the original String before the given position
After that, we put the new character at the position and copy the rest of the characters from the original String in the subsequent positions of the new array.
Other option can be to directly use the already defined methods such as insert().

Accepted Answer

Check Remaining Substrings

The idea behind this approach is to run a loop through every index of the string A.
First, we can check the difference between the lengths of the two strings. If this difference is more than 1, it means that we would need more than 1 operation to convert string A into string B, and hence we can simply return false.
If the character at position i of string A is equal to the character at position i of string B, then we don’t need to perform any operation.
If the characters do not match, then we can perform one of the operations.
If we replace the character of string A with the character at position i of string B, then the remaining substrings of A (starting at position i+1 and ending at last position) and string B (starting at position i+1 and ending at last position) should be the same.
If we delete the ith character of string A, then the substring of string A (starting at position i+1 and ending at last position) and the substring of string B (starting at position i and ending at last position) should be the same. This is because since we deleted ith character from string A, its length reduces by 1.
If we choose to insert a character at this position, then the substring of string A (starting at position i and ending at last position) and the substring of string B (starting at position i+1 and ending at last position) should be the same. This is because we inserted a character into string A, so the remaining characters shift one place to the right.
If the remaining substrings of both the strings are equal after performing any one of these operations, it means that we can transform string A into string B by performing that particular operation.
If all characters are equal, it means that the strings are already equal and we don’t need to perform any operation and we can simply return “True”.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory.

Time Complexity: O(n)Explanation:

O(M+N), where N is the size of the string A and M is the size of the string B.

The time complexity is O(M+N) because we are traversing both the strings and comparing all characters of both strings.

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space Complexity: O(1),



    Where N is the size of the string A and M is the size of the string B.

'''



def isOneAway(a, b):

    lenA, lenB = len(a), len(b)



    # If the difference between the string lengths is more than one, we can never con

    # convert string a into string b by doing only one operation.



    if abs(lenA - lenB) > 1:

        return False

    # We will only iterate uptill the length of the shorter string.



    minLen = min(lenA, lenB)



    for i in range(minLen):

        if a[i] != b[i]:

            validReplace = (a[i+1:] == b[i+1:])

            validInsert = (a[i:] == b[i+1:])

            validDelete = (a[i+1:] == b[i:])



            return validReplace or validInsert or validDelete

    # Since there is no mismatch and the difference between the

    # string lengths is not more than 1, so we can return t

    return True

C++ (g++ 5.4)

/*

    Time Complexity: O(N+M)

    Space Complexity: O(1),



    Where N is the size of the string A and M is the size of the string B.

*/



#include



bool isOneAway(string a, string b) {



    int lenA = a.size(), lenB = b.size();



    // If the difference between the string lengths is more than one, we can never con

    // convert string a into string b by doing only one operation.

    if (abs(lenA - lenB) > 1) {

        return false;

    }



    // We will only iterate uptill the length of the shorter string.

    int minLen = min(lenA, lenB); 



    for (int i = 0; i < minLen; i++) {



        if (a[i] != b[i]) {



            bool validReplace = a.substr(i + 1) == b.substr(i + 1); 

            // If we replace the character.

            

            bool validInsert = a.substr(i)   == b.substr(i + 1);   

            // If we insert a character at this index.



            bool validDelete = a.substr(i + 1) == b.substr(i);     

            // if we delete the character at this index.



            // If after performing any of these operations, the remaining strings are equal,

            // it means that it is possible for us to convert string a into string b.

            return (validReplace || validInsert || validDelete);

        }

    }



    // Since there is no mismatch and the difference between the

    // string lengths is not more than 1, so we can return true.

    return true;

}

Java (SE 1.8)

/*

    Time Complexity: O(N+M)

    Space Complexity: O(1),



    Where N is the size of the string A and M is the size of the string B.

*/



public class Solution 

{

    public static boolean isOneAway(String a, String b) 

    {

        int lenA = a.length(), lenB = b.length();



        // If the difference between the string lengths is more than one, we can never con

        // convert string A into string B by doing only one operation.

        if (Math.abs(lenA - lenB) > 1) 

        {

            return false;

        }

    

        // We will only iterate uptill the length of the shorter string.

        int minLen = Math.min(lenA, lenB); 

    

        for (int i = 0; i < minLen; i++) 

        {

            if (a.charAt(i) != b.charAt(i)) 

            {

                // If we replace the character.

                boolean validReplace =  false;

                if(a.substring(i + 1).compareTo(b.substring(i + 1)) == 0)

                {

                   validReplace = true;

                } 

                

                // If we insert a character at this index.

                boolean validInsert = false;

                if(a.substring(i).compareTo(b.substring(i + 1)) == 0)

                {

                    validInsert = true;

                }   

                

                // if we delete the character at this index.

                boolean validDelete = false;

                if(a.substring(i + 1).compareTo(b.substring(i)) == 0)

                {

                    validDelete = true;

                }      

                

                // If after performing any of these operations, the remaining strings are equal,

                // it means that it is possible for us to convert string A into string B.

                return (validReplace || validInsert || validDelete);

            }

        }

    

        // Since there is no mismatch and the difference between the

        // string lengths is not more than 1, so we can return true.

        return true;

    }

}

Accepted Answer

Using Two Pointers

The idea behind this approach is to maintain a variable that keeps the count of mismatched characters and one pointer for each string and compare the characters at these places
First, we can check the difference between the lengths of the two strings. If this difference is more than 1, it means that we would need more than 1 operation to convert string A into string B, and hence we can simply return false.
If the character at position i of string A is equal to the character at position i of string B, then we don’t need to perform any operation and we can shift both pointers by one place to the right
If the characters do not match, then we can perform one of the operations.
If the length of the first string is more than that of the second string, we know that we have to delete a character from the first string and thus we can increase the count by 1 and can shift the pointer of the first string by one place to the right.
If the length of the first string is less than that of the second string, we know that we have to insert a character into the first string and thus we can increase the count by 1 and can shift the pointer of the second string by one place to the right.
If the length of the first string is equal to that of the second string, we know that we have to replace the character of the first string and thus we can increase the count by 1 and can shift the pointer of the first string as well as of the second string by one place to the right.
If at any point, the value of the count variable becomes more than one, it means that we need to perform more than one operation and we can return false.
We can keep traversing as long as both the pointers are within their respective range (i.e the length of the respective range). As soon as one of the pointers gets out of range, we can stop traversing.
If any of the strings has an extra character at the end we can increase the count by 1.
Finally, if the count is less than or equal to one, it means that string A can be converted into string B by performing any of those operations not more than once and we can return “true”, else it’s not possible and we return “false”.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory.

Time Complexity: O(n)Explanation:

O(M+N), where N is the size of the string A and M is the size of the string B.

The time complexity is O(M+N) because we are traversing both the strings and comparing all characters of both strings.

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space Complexity: O(1),



    Where N is the size of the string A and M is the size of the string B.

'''



def isOneAway(a, b):



    lenA, lenB = len(a), len(b)

    # Initialize a variable to store the number of mismatched characte

    mismatch = 0

    # Initialize one pointer for each string.

    ptrA, ptrB = 0, 0



    while (ptrA < lenA) and (ptrB < lenB):

        if a[ptrA] == b[ptrB]:

            ptrA += 1

            ptrB += 1



        else:

            # If the characters do not match, increment the count.

            mismatch += 1

            # If the mismatched characters become more than one, return False.   

            if mismatch > 1:

                return False



            # If the lengths of both the strings are equal, increment both pointers by 1.

            if lenA == lenB:

                ptrA += 1

                ptrB += 1



            # If the length of string a is more than string b, increment pointer of string a.



            elif lenA > lenB:

                ptrA += 1



            # If the length of string a is less than string b, increment pointer of string b.



            elif lenA < lenB:

                ptrB += 1

    # If there is any extra character at the end of any of the two strings, increment the count.



    if (ptrA < lenA) or (ptrB < lenB):

        mismatch += 1

    # If the number of mismatched characters in less than or equal to one, return True.



    if mismatch <= 1:

        return True

    else:

        return False

Java (SE 1.8)

/*

    Time Complexity: O(N+M)

    Space Complexity: O(1),



    Where N is the size of the string A and M is the size of the string B.

*/



public class Solution 

{

    public static boolean isOneAway(String a, String b) 

    {

        int lenA = a.length(), lenB = b.length();



        // Initialize a variable to store the number of mismatched characters.

        int mismatch = 0;

    

        // Initialize one pointer for each string.

        int ptrA = 0, ptrB = 0;

    

        while (ptrA < lenA && ptrB < lenB) 

        {

            if (a.charAt(ptrA) == b.charAt(ptrB)) 

            {

                ptrA++;

                ptrB++;

            }

            else 

            {

                // If the characters do not match, increment the count.

                mismatch++;

    

                // If the mismatched characters become more than one, return False.

                if (mismatch > 1) 

                {

                    return false;

                }

    

                // If the lengths of both the strings are equal, increment both pointers by 1.

                if (lenA == lenB) 

                {

                    ptrA++;

                    ptrB++;

                }

    

                // If the length of string A is more than string B, increment pointer of string A.

                else if (lenA > lenB) 

                {

                    ptrA++;

                }

    

                // If the length of string A is less than string B, increment pointer of string B.

                else if (lenA < lenB) 

                {

                    ptrB++;

                }

            }

        }



        // If there is any extra character at the end of any of the two strings, increment the count.

        if (ptrA < lenA || ptrB < lenB) 

        {

            mismatch++;

        }

    

        // If the number of mismatched characters in less than or equal to one, return True.

        if (mismatch <= 1) 

        {

            return true;

        }

    

        else {

            return false;

        }

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N+M)

    Space Complexity: O(1),



    Where N is the size of the string A and M is the size of the string B.

*/



#include



bool isOneAway(string a, string b) {



	int lenA = a.size(), lenB = b.size();



	// Initialize a variable to store the number of mismatched characters.

	int mismatch = 0;



	// Initialize one pointer for each string.

	int ptrA = 0, ptrB = 0;



	while (ptrA < lenA and ptrB < lenB) {



		if (a[ptrA] == b[ptrB]) {

			ptrA++;

			ptrB++;

		}



		else {



			// If the characters do not match, increment the count.

			mismatch++;



			// If the mismatched characters become more than one, return False.

			if (mismatch > 1) {

				return false;

			}



			// If the lengths of both the strings are equal, increment both pointers by 1.

			if (lenA == lenB) {

				ptrA++;

				ptrB++;

			}



			// If the length of string a is more than string b, increment pointer of string a.

			else if (lenA > lenB) {

				ptrA++;

			}



			// If the length of string a is less than string b, increment pointer of string b.

			else if (lenA < lenB) {

				ptrB++;

			}

		}



	}



	// If there is any extra character at the end of any of the two strings, increment the count.

	if (ptrA < lenA or ptrB < lenB) {

		mismatch++;

	}



	// If the number of mismatched characters in less than or equal to one, return True.

	if (mismatch <= 1) {

		return 1;

	}



	else {

		return 0;

	}



}

You are given two strings, string A and string B. Your task is to determine whether string A can be transformed into string B by performing only one of the following operations at most one (or maybe zero) time.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top PayPal Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in PayPal Software Developer Intern