The question asks to find the minimum number of left shift operations required to obtain the longest common prefix of two given strings.

• Perform left shift operations on string B to find the longest co...read more

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...read more

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:

1. Concatenate string B with itself. Let’s denote the length of the string A and the string B as M and N respectively.
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 both of them to 0.
3. 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.
4. Keep two pointers i and j. Initialize both of them to 0.
5. Run a loop while i is less than N and j is less than M,and do:
   1. If the ith character of B matches with the jth character of A, then increment both i and j.
   2. If the ith character of B doesn’t match with the jth character of A, then check the value of j i.e
   3. Else If j > 0, then j redirects to lps[j-1] and continue the loop.
   4. If none of the above conditions matches, then increment i by 1.
   5. If the value of j exceeds the max variable, then update the max to j and ans to i-j.
6. Finally, return the ans variable after the loop is over.

For calculating the lps array:

1. Create an lps array of size M, where M is the length of string A and initialize all elements in the array to 0.
2. Keep two pointers i and j. Initialize i as 1 and j as 0.
3. Run a loop till i < M, and do:
   1. 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.
   2. 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.

O(M), where M is the length of the string A.

In the worst case, we are creating the lps array of size M, Hence, the overall space complexity will be O(M).

O(N + M), where M and N are the lengths of the string A and B respectively.

In the worst case, we will be traversing the whole string A and B, but since the lps array for A is already calculated, so the value of j just redirects to lps[j-1] if any mismatch occurs. Hence, the overall complexity will be O(N + M).