Given a string, we need to find the minimum number of rotations required to get the same string.
Examples:
Input : s = "neveropen" Output : 5 Input : s = "aaaa" Output : 1
Method 1: The idea is based on below post.
A Program to check if strings are rotations of each other or not
Step 1 : Initialize result = 0 (Here result is count of rotations)
Step 2 : Take a temporary string equals to original string concatenated with itself.
Step 3 : Now take the substring of temporary string of size same as original string starting from second character (or index 1).
Step 4 : Increase the count.
Step 5 : Check whether the substring becomes equal to original string. If yes, then break the loop. Else go to step 2 and repeat it from the next index.
Python3
# Python 3 program to determine minimum # number of rotations required to yield # same string.# Returns count of rotations to get the# same string back.def findRotations(str): # tmp is the concatenated string. tmp = str + str n = len(str) for i in range(1, n + 1): # substring from i index of # original string size. substring = tmp[i: i+n] # if substring matches with # original string then we will # come out of the loop. if (str == substring): return i return n# Driver codeif __name__ == '__main__': str = "abc" print(findRotations(str))# This code is contributed # by 29AjayKumar. |
3
Time Complexity: O(n2)
Auxiliary Space: O(n). We are using a temporary string of size n for the concatenated string.
Alternate Implementation in Python :
Python3
# Python 3 program to determine minimum # number of rotations required to yield # same string. # inputstring = 'aaaa'check = '' for r in range(1, len(string)+1): # checking the input after each rotation check = string[r:] + string[:r] # following if statement checks if input is # equals to check , if yes it will print r and # break out of the loop if check == string: print(r) break # This code is contributed # by nagasowmyanarayanan. |
1
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(N)
Please refer complete article on Minimum rotations required to get the same string for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!