Last Updated: 7 Jan, 2021
Longest Common Prefix After Rotation
Moderate
Asked in companies
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?
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
Approaches
- Let’s denote the length of A as M and the length of B as N.
- 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.
- 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.
- 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.
- The left shift operation on string B can be done in place as follows.
- reverse(B, 0, 0)
- reverse(B, 1, N-1)
- reverse(B, 0, N-1)
- Finally, return the ans variable after the loop is over.
lengthOfTheCommonPrefix(A, B):
- Let’s denote the length of A as M and the length of B as N.
- Initialize a count variable to 0, which will store the length of the common prefix of A and B.
- Run a loop from 0 to min(N, M). Let’s denote the loop counter as i, and do:
- If A[i] != B[i], then break out of the loop, else increase the count by 1.
- Finally, return the count variable after the loop ends.
In the brute force approach, we perform the left shift operation N-1 number of times on the string B and find the length of the common prefix of A and B, after each left shift operation. By doing this, we may have to check for the same characters again and again and hence, the time complexity increases to O(N*(N+M) in the worst case, where M and N are the lengths of strings A and B respectively.
By observing the property of left shift operation, we get that after K left shift operations, the first K characters of string B are removed and inserted to the end of the string. And we can perform maximum N-1 left shifts because, after the Nth left shift, the string B is converted again to its original form. So, instead of performing left shift again and again, we can concatenate string B with itself. After doing so, the only task that remains is to find out the longest prefix of string A that is present in string B and the index of this longest prefix in string B, which is exactly the number of shift operations needed.
For finding the index of this longest prefix, we can use KMP algorithm in which we precompute the LPS(Longest Proper Prefix that is also a Suffix) array of length M. So, we already know some characters in the next window. In this way, we avoid checking the same matching characters again and again.
Steps:
- Concatenate string B with itself. Let’s denote the length of the string A and the string B as M and N respectively.
- 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 both of them to 0.
- We first compute the LPS array, for which we can implement another function, let’s say kmpPreProcess and pass the string A and its length M as arguments to this function.
- Keep two pointers i and j. Initialize both of them to 0.
- Run a loop while i is less than N and j is less than M,and do:
- If the ith character of B matches with the jth character of A, then increment both i and j.
- If the ith character of B doesn’t match with the jth character of A, then check the value of j i.e
- Else If j > 0, then j redirects to lps[j-1] and continue the loop.
- If none of the above conditions matches, then increment i by 1.
- If the value of j exceeds the max variable, then update the max to j and ans to i-j.
- Finally, return the ans variable after the loop is over.
For calculating the lps array:
- Create an lps array of size M, where M is the length of string A and initialize all elements in the array to 0.
- Keep two pointers i and j. Initialize i as 1 and j as 0.
- Run a loop till i < M, and do:
- If the i th index of A matches with the j th index of A, then store the value j+1 at lps[i] and increment both i and j.
- If the i th index of A doesn’t match with the j th index of A, then check whether j > 0. If j > 0, then j redirects to lps[j-1], else mark lps[i] as 0 and increment i by 1.