Minimum rotations required to get the same String | Set-2
Given a string, we need to find the minimum number of rotations required to get the same string. In this case, we will only consider Left rotations.
Examples:
Input : s = “Beginner”
Output : 5Input : s = “aaaa”
Output :1
Naive approach: The basic approach is to keep rotating the string from the first position and count the number of rotations until we get the initial string.
Efficient Approach : We will follow the basic approach but will try to reduce the time taken in generating rotations.
The idea is as follows:
- Generate a new string of double size of the input string as:
newString = original string excluding first character + original string with the first character. + denotes concatenation here.
- If original string is str = “abcd”, new string will be “bcdabcd”.
- Now, the task remains to search for the original string in the newly generated string and the index where the string is found in the number of rotations required.
- For string matching, we will use KMP algorithm which performs string matching in linear time.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; void computeLPSArray( char * pat, int M, int * lps); // Prints occurrences of txt[] in pat[] int KMPSearch( char * pat, char * txt) { int M = strlen (pat); int N = strlen (txt); // Create lps[] that will hold the longest // prefix suffix values for pattern int lps[M]; // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); // Index for txt[] , // index for pat[] int i = 0; int j = 0; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { return i - j; j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } } // Fills lps[] for given pattern pat[0..M-1] void computeLPSArray( char * pat, int M, int * lps) { // Length of the previous longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // The loop calculates lps[i] for i = 1 to M-1 int i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } } // Returns count of rotations to get the // same string back int countRotations(string s) { // Form a string excluding the first character // and concatenating the string at the end string s1 = s.substr(1, s.size() - 1) + s; // Convert the string to character array char pat[s.length()], text[s1.length()]; strcpy (pat, s.c_str()); strcpy (text, s1.c_str()); // Use the KMP search algorithm // to find it in O(N) time return 1 + KMPSearch(pat, text); } // Driver code int main() { string s1 = "Beginner" ; cout << countRotations(s1); return 0; } |
Java
// Java implementation of the above approach class GFG { // Prints occurrences of txt[] in pat[] static int KMPSearch( char []pat, char []txt) { int M = pat.length; int N = txt.length; // Create lps[] that will hold the longest // prefix suffix values for pattern int lps[] = new int [M]; // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); // Index for txt[] , // index for pat[] int i = 0 ; int j = 0 ; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { return i - j + 1 ; //j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0 ) j = lps[j - 1 ]; else i = i + 1 ; } } return 0 ; } // Fills lps[] for given pattern pat[0..M-1] static void computeLPSArray( char []pat, int M, int []lps) { // Length of the previous longest prefix suffix int len = 0 ; // lps[0] is always 0 lps[ 0 ] = 0 ; // The loop calculates lps[i] for i = 1 to M-1 int i = 1 ; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0 ) { len = lps[len - 1 ]; } else { lps[i] = 0 ; i++; } } } } // Returns count of rotations to get the // same String back static int countRotations(String s) { // Form a String excluding the first character // and concatenating the String at the end String s1 = s.substring( 1 , s.length() - 1 ) + s; // Convert the String to character array char []pat = s.toCharArray(); char []text = s1.toCharArray(); // Use the KMP search algorithm // to find it in O(N) time return 1 + KMPSearch(pat, text); } // Driver code public static void main(String []args) { String s1 = "Beginner" ; System.out.print(countRotations(s1)); } } // This code is contributed by rutvik_56. |
Python3
# Python3 implementation of the above approach # Prints occurrences of txt[] in pat[] def KMPSearch(pat, txt): M = len (pat) N = len (txt) # Create lps[] that will hold the longest # prefix suffix values for pattern lps = [ 0 ] * M # Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps) # Index for txt[] , # index for pat[] i = 0 j = 0 while i < N: if pat[j] = = txt[i]: j + = 1 i + = 1 if j = = M: return i - j j = lps[j - 1 ] # Mismatch after j matches elif i < N and pat[j] ! = txt[i]: # Do not match lps[0..lps[j-1]] characters, # they will match anyway if j ! = 0 : j = lps[j - 1 ] else : i = i + 1 # Fills lps[] for given pattern pat[0..M-1] def computeLPSArray(pat, M, lps): # Length of the previous longest prefix suffix _len = 0 # lps[0] is always 0 lps[ 0 ] = 0 # The loop calculates lps[i] for i = 1 to M-1 i = 1 while i < M: if pat[i] = = pat[_len]: _len + = 1 lps[i] = _len i + = 1 # (pat[i] != pat[_len]) else : # This is tricky. Consider the example. # AAACAAAA and i = 7. The idea is similar # to search step. if _len ! = 0 : _len = lps[_len - 1 ] else : lps[i] = 0 i + = 1 # Returns count of rotations to get the # same string back def countRotations(s): # Form a string excluding the first character # and concatenating the string at the end s1 = s[ 1 : len (s)] + s # Convert the string to character array pat = s[:] text = s1[:] # Use the KMP search algorithm # to find it in O(N) time return 1 + KMPSearch(pat, text) # Driver code s1 = "Beginner" print (countRotations(s1)) # This code is contributed by divyamohan123 |
C#
// C# implementation of the above approach using System; class GFG{ // Prints occurrences of txt[] in pat[] static int KMPSearch( char []pat, char []txt) { int M = pat.Length; int N = txt.Length; // Create lps[] that will hold the longest // prefix suffix values for pattern int []lps = new int [M]; // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); // Index for txt[] , // index for pat[] int i = 0; int j = 0; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { return i - j ; //j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] // characters, they will match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } return 0; } // Fills lps[] for given pattern pat[0..M-1] static void computeLPSArray( char []pat, int M, int []lps) { // Length of the previous longest // prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // The loop calculates lps[i] // for i = 1 to M-1 int i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } } // Returns count of rotations to get the // same string back static int countRotations( string s) { // Form a string excluding the first character // and concatenating the string at the end string s1 = s.Substring(1, s.Length - 1) + s; // Convert the string to character array char []pat = s.ToCharArray(); char []text = s1.ToCharArray(); // Use the KMP search algorithm // to find it in O(N) time return 1 + KMPSearch(pat, text); } // Driver code public static void Main( params string []args) { string s1 = "Beginner" ; Console.Write(countRotations(s1)); } } // This code is contributed by pratham76 |
Javascript
<script> // JavaScript implementation of the above approach // Prints occurrences of txt[] in pat[] function KMPSearch(pat, txt) { let M = pat.length; let N = txt.length; // Create lps[] that will hold the longest // prefix suffix values for pattern let lps = new Array(M); lps.fill(0); // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); // Index for txt[] , // index for pat[] let i = 0; let j = 0; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { return i - j ; //j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] // characters, they will match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } return 0; } // Fills lps[] for given pattern pat[0..M-1] function computeLPSArray(pat, M, lps) { // Length of the previous longest // prefix suffix let len = 0; // lps[0] is always 0 lps[0] = 0; // The loop calculates lps[i] // for i = 1 to M-1 let i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } } // Returns count of rotations to get the // same string back function countRotations(s) { // Form a string excluding the first character // and concatenating the string at the end let s1 = s.substring(1, s.length) + s; // Convert the string to character array let pat = s.split( '' ); let text = s1.split( '' ); // Use the KMP search algorithm // to find it in O(N) time return 1 + KMPSearch(pat, text); } let s1 = "Beginner" ; document.write(countRotations(s1)); </script> |
Output:
5
Time Complexity: O(N).
Auxiliary Space: O(N), where N is the length of the given string,