Minimum Rotations

Easy
0/40
Average time to solve is 10m
profile
Contributed by
14 upvotes
Asked in companies
AdobeUnthinkable SolutionsJosh Technology Group

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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'.
Sample Input 1 :
1
5
ninja
Sample Output 1 :
5
Explanation of Sample Input 1 :
After five rotations we get the same string i.e “ninja”.
Sample Input 2 :
1
5
ccccc
Sample Output 2 :
1
Explanation of Sample Input 2 :
Just after one rotation, we get the same string i.e “ccccc”.
Hint

Try to generate all possible strings starting from each index.

Approaches (2)
Brute Force Approach

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.
Time Complexity

O(N^2), where N is the length of the string S.

 

There are N characters and for each character, we’ll be doing N operations Hence, the overall Time Complexity is O(N^2).

Space Complexity

O(1).

 

We are using constant extra memory. Hence, the overall Time Complexity is O(1). 

Code Solution
(100% EXP penalty)
Minimum Rotations
Full screen
Console