Check if Strings Are Rotations of Each Other
Last Updated : 25 Oct, 2024
Given two string s1 and s2 of same length, the task is to check whether s2 is a rotation of s1.
Examples:
Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: After 2 right rotations, s1 will become equal to s2.
Input: s1 = "aab", s2 = "aba"
Output: true
Explanation: After 1 left rotation, s1 will become equal to s2.
Input: s1 = "abcd", s2 = "acbd"
Output: false
Explanation: Strings are not rotations of each other.
[Naive Approach] Generating all rotations - O(n^2) Time and O(1) Space
The idea is to generate all possible rotations of the first string and check if any of these rotations match the second string. If any rotation matches, the two strings are rotations of each other, otherwise they are not.
C++ // C++ program to check two string for rotation // by generating all rotations #include <iostream> using namespace std; // Function to check if s1 and s2 are rotations of each other bool areRotations(string &s1, string &s2) { int n = s1.size(); // generate and check all possible rotations of s1 for (int i = 0; i < n; ++i) { // if current rotation is equal to s2 return true if (s1 == s2) return true; // right rotate s1 char last = s1.back(); s1.pop_back(); s1 = last + s1; } return false; } int main() { string s1 = "aab"; string s2 = "aba"; cout << (areRotations(s1, s2) ? "true" : "false"); return 0; } // C program to check two strings for rotation // by generating all rotations #include <stdio.h> #include <string.h> // Function to check if s1 and s2 are rotations of each other int areRotations(char s1[], char s2[]) { int n = strlen(s1); // Generate and check all possible rotations of s1 for (int i = 0; i < n; ++i) { // If current rotation is equal to s2, return true if (strcmp(s1, s2) == 0) return 1; // Right rotate s1 char last = s1[n-1]; for (int j = n-1; j > 0; j--) { s1[j] = s1[j-1]; } s1[0] = last; } return 0; } int main() { char s1[] = "aab"; char s2[] = "aba"; printf("%s", areRotations(s1, s2) ? "true" : "false"); return 0; } // Java program to check two strings for rotation // by generating all rotations class GfG { // Function to check if s1 and s2 are rotations of each other static boolean areRotations(String s1, String s2) { int n = s1.length(); // Generate and check all possible rotations of s1 for (int i = 0; i < n; ++i) { // If current rotation is equal to s2, return true if (s1.equals(s2)) { return true; } // Right rotate s1 char last = s1.charAt(s1.length() - 1); s1 = last + s1.substring(0, s1.length() - 1); } return false; } public static void main(String[] args) { String s1 = "aab"; String s2 = "aba"; System.out.println(areRotations(s1, s2)); } } # Python program to check two strings for rotation # by generating all rotations # Function to check if s1 and s2 are rotations of each other def areRotations(s1, s2): n = len(s1) # Generate and check all possible rotations of s1 for _ in range(n): # If current rotation is equal to s2, return true if s1 == s2: return True # Right rotate s1 s1 = s1[-1] + s1[:-1] return False if __name__ == "__main__": s1 = "aab" s2 = "aba" print("true" if areRotations(s1, s2) else "false") // C# program to check two strings for rotation // by generating all rotations using System; class GfG { // Function to check if s1 and s2 are rotations of each other static bool areRotations(string s1, string s2) { int n = s1.Length; // Generate and check all possible rotations of s1 for (int i = 0; i < n; ++i) { // If current rotation is equal to s2, return true if (s1 == s2) { return true; } // Right rotate s1 char last = s1[s1.Length - 1]; s1 = last + s1.Substring(0, s1.Length - 1); } return false; } static void Main() { string s1 = "aab"; string s2 = "aba"; Console.WriteLine(areRotations(s1, s2) ? "true" : "false"); } } // JavaScript program to check two strings for rotation // by generating all rotations // Function to check if s1 and s2 are rotations of each other function areRotations(s1, s2) { let n = s1.length; // Generate and check all possible rotations of s1 for (let i = 0; i < n; i++) { // If current rotation is equal to s2, return true if (s1 === s2) { return true; } // Right rotate s1 let last = s1[s1.length - 1]; s1 = last + s1.slice(0, s1.length - 1); } return false; } // Driver Code let s1 = "aab"; let s2 = "aba"; console.log(areRotations(s1, s2) ? "true" : "false"); [Expected Approach] Using KMP Algorithm - O(n) Time and O(n) Space
The idea is that when a string is concatenated with itself, all possible rotations of the string will naturally appear as substrings within this concatenated string. To determine if another string is a rotation of the first, we can use KMP Algorithm to check if the second string exists as a substring in the concatenated form of the first string.
C++ // C++ program to check if two given strings // are rotations of each other using KMP Algorithm #include <iostream> #include <vector> using namespace std; vector<int> computeLPSArray(string& pat) { int n = pat.size(); vector<int> lps(n); // Length of the previous longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // If the characters match, increment len // and extend the matching prefix if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // If there is a mismatch else { // If len is not zero, update len to // last known prefix length if (len != 0) { len = lps[len - 1]; } // No prefix matches, set lps[i] = 0 // and move to the next character else { lps[i] = 0; i++; } } } return lps; } // Function to check if s1 and s2 are rotations of each other bool areRotations(string &s1, string &s2) { string txt = s1 + s1; string pat = s2; // search the pattern string s2 in the concatenation string int n = txt.length(); int m = pat.length(); // Create lps[] that will hold the longest prefix suffix // values for pattern vector<int> lps = computeLPSArray(pat); int i = 0; int j = 0; while (i < n) { if (pat[j] == txt[i]) { j++; i++; } if (j == m) { return true; } // 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 false; } int main() { string s1 = "aab"; string s2 = "aba"; cout << (areRotations(s1, s2) ? "true" : "false"); } // C program to check if two given strings are // rotations of each other using KMP Algorithm #include <stdio.h> #include <string.h> int* computeLPSArray(char* pat) { int n = strlen(pat); int* lps = (int*)malloc(n * sizeof(int)); // Length of the previous longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // If the characters match, increment len // and extend the matching prefix if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // If there is a mismatch else { // If len is not zero, update len to // last known prefix length if (len != 0) { len = lps[len - 1]; } // No prefix matches, set lps[i] = 0 // and move to the next character else { lps[i] = 0; i++; } } } return lps; } // Function to check if s1 and s2 are rotations of each other int areRotations(char *s1, char *s2) { char* txt = (char*)malloc(strlen(s1) * 2 + 1); strcpy(txt, s1); strcat(txt, s1); char* pat = s2; // search the pattern string s2 in the concatenated string int n = strlen(txt); int m = strlen(pat); // Create lps[] that will hold the longest prefix suffix // values for pattern int* lps = computeLPSArray(pat); int i = 0; int j = 0; while (i < n) { if (pat[j] == txt[i]) { j++; i++; } if (j == m) { return 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; } int main() { char s1[] = "aab"; char s2[] = "aba"; printf("%s", (areRotations(s1, s2) ? "true" : "false")); return 0; } // Java program to check if two given strings are rotations // of each other using KMP Algorithm import java.util.Arrays; class GfG { static int[] computeLPSArray(String pat) { int n = pat.length(); int[] lps = new int[n]; // Length of the previous longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // If the characters match, increment len // and extend the matching prefix if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } // If there is a mismatch else { // If len is not zero, update len to // last known prefix length if (len != 0) { len = lps[len - 1]; } // No prefix matches, set lps[i] = 0 // and move to the next character else { lps[i] = 0; i++; } } } return lps; } // Function to check if s1 and s2 are rotations of each other static boolean areRotations(String s1, String s2) { String txt = s1 + s1; String pat = s2; // search the pattern string s2 in the concatenation string int n = txt.length(); int m = pat.length(); // Create lps[] that will hold the longest prefix suffix // values for pattern int[] lps = computeLPSArray(pat); int i = 0; int j = 0; while (i < n) { if (pat.charAt(j) == txt.charAt(i)) { j++; i++; } if (j == m) { return true; } // Mismatch after j matches else if (i < n && pat.charAt(j) != txt.charAt(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 false; } public static void main(String[] args) { String s1 = "aab"; String s2 = "aba"; System.out.println(areRotations(s1, s2) ? "true" : "false"); } } # Python program to check if two given strings are # rotations of each other using KMP Algorithm def computeLPSArray(pat): n = len(pat) lps = [0] * n # Length of the previous longest prefix suffix patLen = 0 # lps[0] is always 0 lps[0] = 0 # loop calculates lps[i] for i = 1 to n-1 i = 1 while i < n: # If the characters match, increment len # and extend the matching prefix if pat[i] == pat[patLen]: patLen += 1 lps[i] = patLen i += 1 # If there is a mismatch else: # If len is not zero, update len to # last known prefix length if patLen != 0: patLen = lps[patLen - 1] # No prefix matches, set lps[i] = 0 # and move to the next character else: lps[i] = 0 i += 1 return lps # Function to check if s1 and s2 are rotations of each other def areRotations(s1, s2): txt = s1 + s1 pat = s2 # search the pattern string s2 in the concatenation string n = len(txt) m = len(pat) # Create lps[] that will hold the longest prefix suffix # values for pattern lps = computeLPSArray(pat) i = 0 j = 0 while i < n: if pat[j] == txt[i]: j += 1 i += 1 if j == m: return True # 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 += 1 return False if __name__ == "__main__": s1 = "aab" s2 = "aba" print("true" if areRotations(s1, s2) else "false") // C# program to check if two given strings are rotations // of each other using KMP Algorithm using System; using System.Collections.Generic; class GfG { static int[] ComputeLPSArray(string pat) { int n = pat.Length; int[] lps = new int[n]; // Length of the previous longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // If the characters match, increment len // and extend the matching prefix if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // If there is a mismatch else { // If len is not zero, update len to // last known prefix length if (len != 0) { len = lps[len - 1]; } // No prefix matches, set lps[i] = 0 // and move to the next character else { lps[i] = 0; i++; } } } return lps; } // Function to check if s1 and s2 are rotations of each other static bool AreRotations(string s1, string s2) { string txt = s1 + s1; string pat = s2; // search the pattern string s2 in the concatenation string int n = txt.Length; int m = pat.Length; // Create lps[] that will hold the longest prefix suffix // values for pattern int[] lps = ComputeLPSArray(pat); int i = 0; int j = 0; while (i < n) { if (pat[j] == txt[i]) { j++; i++; } if (j == m) { return true; } // 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++; } } return false; } static void Main() { string s1 = "aab"; string s2 = "aba"; Console.WriteLine(AreRotations(s1, s2) ? "true" : "false"); } } // JavaScript program to check if two given strings // are rotations of each other using KMP Algorithm function computeLPSArray(pat) { let n = pat.length; let lps = new Array(n).fill(0); // Length of the previous longest prefix suffix let len = 0; // lps[0] is always 0 lps[0] = 0; // loop calculates lps[i] for i = 1 to n-1 let i = 1; while (i < n) { // If the characters match, increment len // and extend the matching prefix if (pat[i] === pat[len]) { len++; lps[i] = len; i++; } // If there is a mismatch else { // If len is not zero, update len to // last known prefix length if (len !== 0) { len = lps[len - 1]; } // No prefix matches, set lps[i] = 0 // and move to the next character else { lps[i] = 0; i++; } } } return lps; } // Function to check if s1 and s2 are rotations of each other function areRotations(s1, s2) { let txt = s1 + s1; let pat = s2; // search the pattern string s2 in the concatenation string let n = txt.length; let m = pat.length; // Create lps[] that will hold the longest prefix suffix // values for pattern let lps = computeLPSArray(pat); let i = 0; let j = 0; while (i < n) { if (pat[j] === txt[i]) { j++; i++; } if (j === m) { return true; } // 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++; } } return false; } // Driver Code const s1 = "aab"; const s2 = "aba"; console.log(areRotations(s1, s2) ? "true" : "false"); [Alternate Approach] Using Built-in Method
This approach is similar to the previous approach, but here we are using built-in methods to find a pattern string inside other string.
C++ // C++ program to check if two given strings // are rotations of each other #include <iostream> using namespace std; // Function to check if s1 and s2 are rotations of each other bool areRotations(string &s1, string &s2) { s1 += s1; // find s2 in concatenated string return s1.find(s2) != string::npos; } int main() { string s1 = "aab"; string s2 = "aba"; cout << (areRotations(s1, s2) ? "true" : "false"); } // C program to check if two given strings are rotations of each other #include <stdio.h> #include <string.h> #include <stdlib.h> // Function to check if s1 and s2 are rotations of each other int areRotations(char* s1, char* s2) { // Concatenate s1 with itself int len = strlen(s1); char* concat = (char*)malloc(2 * len + 1); strcpy(concat, s1); strcat(concat, s1); // find s2 in concatenated string int result = strstr(concat, s2) != NULL; free(concat); return result; } int main() { char s1[] = "aab"; char s2[] = "aba"; printf("%s\n", areRotations(s1, s2) ? "true" : "false"); return 0; } // Java program to check if two given strings are rotations of each other class GfG { // Function to check if s1 and s2 are rotations of each other static boolean areRotations(String s1, String s2) { s1 = s1 + s1; // find s2 in concatenated string return s1.contains(s2); } public static void main(String[] args) { String s1 = "aab"; String s2 = "aba"; System.out.println(areRotations(s1, s2)); } } # Python program to check if two given strings are rotations of each other # Function to check if s1 and s2 are rotations of each other def areRotations(s1, s2): s1 = s1 + s1 # find s2 in concatenated string return s2 in s1 if __name__ == "__main__": s1 = "aab" s2 = "aba" print("true" if areRotations(s1, s2) else "false") // C# program to check if two given strings are rotations of each other using System; class GfG { // Function to check if s1 and s2 are rotations of each other static bool areRotations(string s1, string s2) { s1 = s1 + s1; // find s2 in concatenated string return s1.Contains(s2); } static void Main() { string s1 = "aab"; string s2 = "aba"; Console.WriteLine(areRotations(s1, s2) ? "true" : "false"); } } // JavaScript program to check if two given strings are rotations of each other // Function to check if s1 and s2 are rotations of each other function areRotations(s1, s2) { s1 += s1; // find s2 in concatenated string return s1.includes(s2); } // driver code const s1 = "aab"; const s2 = "aba"; console.log(areRotations(s1, s2) ? "true" : "false"); Note: Time complexity of built-in methods differs in different languages.
Similar Reads
Check if two strings are permutation of each other Write a function to check whether two given strings are Permutation of each other or not. A Permutation of a string is another string that contains same characters, only the order of characters can be different. For example, "abcd" and "dabc" are Permutation of each other. We strongly recommend that
13 min read
Check if strings are rotations of each other or not | Set 2 Given two strings s1 and s2, check whether s2 is a rotation of s1. Examples: Input : ABACD, CDABA Output : True Input : GEEKS, EKSGE Output : True We have discussed an approach in earlier post which handles substring match as a pattern. In this post, we will be going to use KMP algorithm's lps (long
6 min read
Check if two numbers are bit rotations of each other or not Given two positive integers x and y (0 < x, y < 2^32), check if one integer is obtained by rotating bits of the other. Bit Rotation: A rotation (or circular shift) is an operation similar to a shift except that the bits that fall off at one end are put back to the other end. Examples: Input :
6 min read
POTD Solutions | 14 Nov'23 | Check if strings are rotations of each other or not View all POTD Solutions Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of String but will also help you build up problem-solving
3 min read
Javascript Program to Check if strings are rotations of each other or not | Set 2 Given two strings s1 and s2, check whether s2 is a rotation of s1. Examples: Input : ABACD, CDABAOutput : TrueInput : GEEKS, EKSGEOutput : TrueWe have discussed an approach in earlier post which handles substring match as a pattern. In this post, we will be going to use KMP algorithm's lps (longest
2 min read
Check if all rows of a matrix are circular rotations of each other Given a matrix of n*n size, the task is to find whether all rows are circular rotations of each other or not. Examples: Input: mat[][] = 1, 2, 3 3, 1, 2 2, 3, 1 Output: Yes All rows are rotated permutation of each other. Input: mat[3][3] = 1, 2, 3 3, 2, 1 1, 3, 2 Output: No Explanation : As 3, 2, 1
8 min read