Longest Common Prefix After Rotation

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
17 upvotes
Asked in companies
IBMMicrosoftOLX Group

Problem statement

You are given two strings 'A' and 'B' where string 'A' is fixed. But you can perform left shift operations on string B any number of times.

Your task is to find out the minimum number of left-shift operations required in order to obtain the longest common prefix of string 'A' and 'B'.

Note:

Left shift is defined as a single circular rotation on the string after which the first character becomes the last character and all other characters are shifted one index to the left.
For Example: 
If A = “an”, B = “can”.
After performing one left shift operation, string B becomes “anc”.
After performing two left shift operations, string B becomes “nca”.
Follow Up: 
Can you solve this in linear time and space complexity?
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. 
Then, the T test cases follow.

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

The second line of each test case contains the string B.
Output format: 
For each test case, print the minimum number of left shift operations required in order to obtain the longest common prefix of string A and B.
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|, |B| <= 5 * 10^4
Where |A| and |B| denote the length of string, A and B respectively.   

All the characters of the string A and B contain lowercase English letters only.

Time limit: 1 second
Sample Input 1:
2
on
soon
an
an
Sample Output 1:
2
0
Explanation for sample 1:
For the first test case, the common prefix of A and B is .””
After one left shift, the string B becomes “oons”, now the common prefix is “o”.
After two left shifts, the string B becomes “onso”, now the common prefix is “on”.
After three left shifts, the string B becomes “nsoo”, now the common prefix is “”.
(We do not need to perform one more left shift, because if the number of left-shift operations is equal to the length of the string, then we get the original string. For example, here if we perform one more shift, then we get the string “soon” which was the original string.)
So after two left shifts, we get the longest common prefix i.e. “on”. Hence, the answer is 2.

For the second test case, the common prefix of A and B is “an”.
After one left shift, the string B becomes “na”, now the common prefix is “”.
So we get the longest common prefix without performing any shifts. Hence, the answer is 0.
Sample Input 2:
2
abc 
def
sorry
personal
Sample output 2:
0
3
Explanation for sample 2:
For the first test case, the common prefix of A and B is “”.
After one left shift, the string B becomes “efd”, now the common prefix is again “”.
After two left shifts, the string B becomes “fde”, now the common prefix is again “”.
Here the length of the longest common prefix is 0, as there is no common prefix in all the cases. So we get the longest common prefix without performing any shifts. Hence, the answer is 0.
For the second test case, the common prefix of A and B is “”.
After one left shift, the string B becomes “ersonalp”, now the common prefix is “”.
After two left shifts, the string B becomes “rsonalpe”, now the common prefix is “”.
After three left shifts, the string B becomes “sonalper”, now the common prefix is “so”.
After four left shifts, the string B becomes “onalpers”, now the common prefix is “”.
After five left shifts, the string B becomes “nalperso”, now the common prefix is “”.
After six left shifts, the string B becomes “alperson”, now the common prefix is “”.
After seven left shifts, the string B becomes “lpersona”, now the common prefix is “”.

So after three left shifts, we get the longest common prefix i.e. “so”. Hence, the answer is 3.
Hint

Think of brute force solution by shifting the string B one by one and keep track of the longest common prefix after each shift.

Approaches (2)
Brute Force
  1. Let’s denote the length of A as M and the length of B as N.
  2. Declare an ans variable to store the minimum number of left shifts required and a max variable in order to store the length of the longest common prefix encountered so far. Initialize the ans variable to 0.
  3. Find out the common prefix of A and B and initialize max to the length of the common prefix. The length of the common prefix between two strings can be obtained by implementing a function let’s say lengthOfTheCommonPrefix and passing A and B as arguments to this function.
  4. We run a loop from 1 to N-1. Let’s denote the loop counter as i. In each iteration, we left shift the string B by one character and find the length of the common prefix of A and B by calling the lengthOfTheCommonPrefix function. If this length is greater than the max variable, then update the max to this length and update the ans to i.
  5. The left shift operation on string B can be done in place as follows.
    1. reverse(B, 0, 0)
    2. reverse(B, 1, N-1)
    3. reverse(B, 0, N-1)
  6. Finally, return the ans variable after the loop is over.

 

lengthOfTheCommonPrefix(A, B):

  1. Let’s denote the length of A as M and the length of B as N.
  2. Initialize a count variable to 0, which will store the length of the common prefix of A and B.
  3. Run a loop from 0 to min(N, M). Let’s denote the loop counter as i, and do:
    1. If A[i] != B[i], then break out of the loop, else increase the count by 1.
  4. Finally, return the count variable after the loop ends.
Time Complexity

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

 

In the worst case, we will be traversing the whole string B, and for each iteration, we will perform the left shift operation which takes O(N) time, and then we will traverse the whole string A in the lengthOfTheCommonPrefix function, which takes O(M) time. So, the time needed for one iteration is O(N+M). Hence, the overall time complexity is O(N*(N+M)).

Space Complexity

O(1).

 

In the worst case, a constant space is required.

Code Solution
(100% EXP penalty)
Longest Common Prefix After Rotation
Full screen
Console