C++ Program for Minimum rotations required to get the same string
Given a string, we need to find the minimum number of rotations required to get the same string.
Examples:
Input : s = "Beginner" Output : 5 Input : s = "aaaa" Output : 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 equal 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.
Below is the implementation of the above approach:
C++
// C++ program to determine minimum number // of rotations required to yield same // string. #include <iostream> using namespace std; // Returns count of rotations to get the // same string back. int findRotations(string str) { // tmp is the concatenated string. string tmp = str + str; int n = str.length(); for ( int i = 1; i <= n; i++) { // substring from i index of original // string size. string substring = tmp.substr(i, str.size()); // if substring matches with original string // then we will come out of the loop. if (str == substring) return i; } return n; } // Driver code int main() { string str = "abc" ; cout << findRotations(str) << endl; return 0; } |
Output
3
Time Complexity: O(n2)
Auxiliary Space: O(n)
Please refer complete article on Minimum rotations required to get the same string for more details!