Last Updated: 4 Feb, 2021
Minimum Rotations
Easy
Asked in companies
You’re given a string 'S' of length 'N'. Your task is to find the minimum number of rotations to get the same string 'S'.
NOTE :
The string only consists of lowercase English alphabets.
Input Format :
The first line of input contains 'T', the number of test cases.
The first line of each test case contains an integer 'N', denoting the length of string 'S'.
The second line of each test case contains the string 'S'.
Output Format :
The only line of output of each test case should contain an integer denoting the minimum rotations required to get the same string 'S'.
Print the output of each test case in a separate line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= N <= 10 ^ 4
Time Limit: 1 sec
The string 'S' only contains lowercase English characters.
Where 'T' denotes the number of test cases and 'N' denotes the length of string 'S'.
Approaches
The idea that we will be using in this approach is that we start from position 1 and start generating all substrings of length N and check if this substring is equal to the original string S or not. Let’s see how we will achieve this.
- Start by making a string named concat of length 2*N, which is made by concatenating S with itself(S+S).
- Now run a loop(loop variable i) from 1 till N-1 and for this i, check if a substring that starts from concat[i] and is of length N equals to S or not.
- If it is equal to S, simply return i and exit the loop.
- If we don’t find any such substring then we return N as our answer.
For Example: N = 3 and S = abc
- C = S + S = “abcabc”
- We then run a loop(loop variable i) from 1 till 3 and check if a substring(of C) of length 3 is equal to S or not.
- 1st substring is bca which is not equal to S, hence we move further.
- 2nd substring is cab which is also not equal to S, hence we move further.
- 3rd substring is abc which is equal to S. Therefore we return i = 3 as our answer.
The idea that we will be using in this approach is that we will generate a string named C of length 2*N - 1. This string will be made by removing the first character from string S and then concatenating it with string S(with the first character as well) and in this string check when S occurs.
For example, if S = code, then C = odecode.
Now we are almost done and we just have to traverse this string C once and the index where we encounter string S, that index is the number of rotations required to get back to S. For this string matching, we’ll use the famous Knuth-Morris-Pratt algorithm(KMP). Let’s see how will we reach our final answer.
- Start by making a string C of length 2*N - 1 which will be made by removing the first character of S and then adding another S to this string but this time we won’t be removing the first character.
- Using KMP algorithm find the position at which S appears in C and assign this value to an integer variable ans.
- Finally return ans+1, which is our final answer. (adding 1 because we are using KMP and in KMP algorithm we’ll be using 0 based indexing).
For example: N = 4 and S = abcd
- String C = “bcdabcd”
- We can see that String S appears at position 4 in C.
- Hence we return 4, which is our answer.