One Away

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in companies
PayPalGoldman SachsMicrosoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
abcde
abcd
Sample Output 1 :
True
Explanation For Sample Input 1 :
For the strings “abcde” and “abcd”, we can observe that string B has one less character than the string A and all the characters of the strings are matching up to this length and in fact string A has one extra character. This means that we can simply delete this extra character and can get a string equal to the string B as the resultant string. Since we only used one of the operations only once, we can return “true”.
Sample Input 2 :
1
stbr
start
Sample Output 2 :
False
Explanation For Sample Input 2 :
For the strings “stbr” and “start”, we can observe that we require at least two operations to convert string A into string B. In one operation, we can replace ‘b’ with ‘a’ and we get “star” as the resultant string. This resultant string is not equal to the string B, “start”. We still need one more operation to convert it into string B. We can achieve this by adding ‘t’ to the resultant string so it will become “start”  But this would take two operations. So we print “false”.
Hint

After performing an operation, the remaining substrings must be equal.

Approaches (2)
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”.
Time Complexity

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.

Space Complexity

O(1).

 

As we are using constant extra memory.

Code Solution
(100% EXP penalty)
One Away
Full screen
Console