Check if a string can be obtained by rotating another string 2 places
Given two strings, the task is to find if a string can be obtained by rotating another string by two places.
Examples:
Input: string1 = “amazon”, string2 = “azonam”
Output: Yes
Explanation: Rotating string1 by 2 places in anti-clockwise gives the string2.Input: string1 = “amazon”, string2 = “onamaz”
Output: Yes
Explanation: Rotating string1 by 2 places in clockwise gives the string2.
Asked in: Amazon Interview
Approach 1 (by Rotating String Clockwise and Anti-clockwise):
The idea is to Rotate the String1 in both clockwise and ant-clockwise directions. Then if this rotated string is equal to String2.
Illustration:
str1 = “amazon”
str2 = “azonam”Initialise: clock_rot = “”, anticlock_rot = “”
str1 after 2 places clockwise rotation:
clock_rot = “onamaz”str1 after 2 places anti-clockwise rotation:
anticlock_rot = “azonam”Therefore, anticlock_rot and str2 are same.
Hence, str2 can be achieved from str1
Follow the steps below to solve the problem:
- Initialize two empty strings which keep the clockwise and anticlockwise strings respectively.
- After rotating the str1 compare both clockwise and anticlockwise strings with str2.
- If any of them matches the str2 return true, otherwise false.
Below is the implementation of the above approach.
C++
// C++ program to check if a string is two time // rotation of another string. #include<bits/stdc++.h> using namespace std; // Function to check if string2 is obtained by // string 1 bool isRotated(string str1, string str2) { if (str1.length() != str2.length()) return false ; if (str1.length()<2){ return str1.compare(str2) == 0; } string clock_rot = "" ; string anticlock_rot = "" ; int len = str2.length(); // Initialize string as anti-clockwise rotation anticlock_rot = anticlock_rot + str2.substr(len-2, 2) + str2.substr(0, len-2) ; // Initialize string as clock wise rotation clock_rot = clock_rot + str2.substr(2) + str2.substr(0, 2) ; // check if any of them is equal to string1 return (str1.compare(clock_rot) == 0 || str1.compare(anticlock_rot) == 0); } // Driver code int main() { string str1 = "Beginner" ; string str2 = "eksge" ; isRotated(str1, str2) ? cout << "Yes" : cout << "No" ; return 0; } |
Java
// Java program to check if a string is two time // rotation of another string. class Test { // Method to check if string2 is obtained by // string 1 static boolean isRotated(String str1, String str2) { if (str1.length() != str2.length()) return false ; if (str1.length() < 2 ) { return str1.equals(str2); } String clock_rot = "" ; String anticlock_rot = "" ; int len = str2.length(); // Initialize string as anti-clockwise rotation anticlock_rot = anticlock_rot + str2.substring(len- 2 , len) + str2.substring( 0 , len- 2 ) ; // Initialize string as clock wise rotation clock_rot = clock_rot + str2.substring( 2 ) + str2.substring( 0 , 2 ) ; // check if any of them is equal to string1 return (str1.equals(clock_rot) || str1.equals(anticlock_rot)); } // Driver method public static void main(String[] args) { String str1 = "Beginner" ; String str2 = "eksge" ; System.out.println(isRotated(str1, str2) ? "Yes" : "No" ); } } |
Python3
# Python 3 program to check if a string # is two time rotation of another string. # Function to check if string2 is # obtained by string 1 def isRotated(str1, str2): if ( len (str1) ! = len (str2)): return False if ( len (str1) < 2 ): return str1 = = str2 clock_rot = "" anticlock_rot = "" l = len (str2) # Initialize string as anti-clockwise rotation anticlock_rot = (anticlock_rot + str2[l - 2 :] + str2[ 0 : l - 2 ]) # Initialize string as clock wise rotation clock_rot = clock_rot + str2[ 2 :] + str2[ 0 : 2 ] # check if any of them is equal to string1 return (str1 = = clock_rot or str1 = = anticlock_rot) # Driver code if __name__ = = "__main__" : str1 = "Beginner" str2 = "eksge" if isRotated(str1, str2): print ( "Yes" ) else : print ( "No" ) # This code is contributed by ita_c |
C#
using System; // C# program to check if a string is two time // rotation of another string. public class Test { // Method to check if string2 is obtained by // string 1 public static bool isRotated( string str1, string str2) { if (str1.Length != str2.Length) { return false ; } if (str1.Length < 2) { return str1.Equals(str2); } string clock_rot = "" ; string anticlock_rot = "" ; int len = str2.Length; // Initialize string as anti-clockwise rotation anticlock_rot = anticlock_rot + str2.Substring(len - 2, len - (len - 2)) + str2.Substring(0, len - 2); // Initialize string as clock wise rotation clock_rot = clock_rot + str2.Substring(2) + str2.Substring(0, 2); // check if any of them is equal to string1 return (str1.Equals(clock_rot) || str1.Equals(anticlock_rot)); } // Driver code public static void Main( string [] args) { string str1 = "Beginner" ; string str2 = "eksge" ; Console.WriteLine(isRotated(str1, str2) ? "Yes" : "No" ); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to check if a // string is two time rotation of // another string. // Method to check if string2 is // obtained by string 1 function isRotated(str1, str2) { if (str1.length != str2.length) return false ; if (str1.length < 2) { return str1.localeCompare(str2); } let clock_rot = "" ; let anticlock_rot = "" ; let len = str2.length; // Initialize string as anti-clockwise rotation anticlock_rot = anticlock_rot + str2.substring(len - 2, len + 1) + str2.substring(0, len - 1) ; // Initialize string as clock wise rotation clock_rot = clock_rot + str2.substring(2, str2.length - 2 + 1) + str2.substring(0, 2 + 1); // Check if any of them is equal to string1 return (str1.localeCompare(clock_rot) || str1.localeCompare(anticlock_rot)); } // Driver code let str1 = "Beginner" ; let str2 = "eksge" ; document.write(isRotated(str1, str2) ? "Yes" : "No" ); // This code is contributed by rag2127 </script> |
Yes
Time Complexity: O(n), Time is taken to rotate the string and then compare the string.
Auxiliary Space: O(n), Space for storing clockwise and anticlockwise strings.
Approach 2(Without Using auxiliary space):
We could check directly if the string is rotated or not by comparing the two strings.
Illustration:
Steps –
- Check if the string is rotated in clockwise manner.
- Check if the string is rotated in anticlockwise manner.
- Return true if any one of the above is true
We compare for clockwise and anticlockwise by using for loops and the modulo operator-
Note that –
For clockwise – str1[i] == str2[(i + 2) % n]
For anticlockwise – str1[(i + 2) % n] == str2[i]
Here n is length of string
Check using the above two conditions and the problem will be solved!
Below is the implementation of the above approach:
C++
// C++ code to find if string is rotated by 2 positions #include <iostream> using namespace std; bool isRotated(string str1, string str2) { // Your code here // clockwise direction check int n = str1.length(); bool clockwise = true , anticlockwise = true ; for ( int i = 0; i < n; i++) { if (str1[i] != str2[(i + 2) % n]) { clockwise = false ; // not rotated clockwise break ; } } for ( int i = 0; i < n; i++) { if (str1[(i + 2) % n] != str2[i]) { anticlockwise = false ; // not rotated anticlockwise break ; } } return clockwise or anticlockwise; // if any of both is true, return true } int main() { string str1 = "Beginner" ; string str2 = "eksge" ; isRotated(str1, str2) ? cout << "Yes" : cout << "No" ; return 0; } //code contributed by Anshit Bansal |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { //Method to check if string2 is obtained by string1 static boolean isRotated(String str1, String str2) { int n = str1.length(); int m = str2.length(); if (n != m) //check both the string length equal or not return false ; boolean clockwise = true ; boolean anticlockwise = true ; //check clockwise rotation is possible or not for ( int i = 0 ; i < n; i++) { if (str1.charAt(i)!= str2.charAt((i + 2 ) % n)) { clockwise = false ; break ; } } // check anticlockwise rotation is possible or not for ( int i = 0 ; i < m; i++) { if (str1.charAt((i + 2 ) % n)!= str2.charAt(i)) { anticlockwise = false ; break ; } } return (clockwise || anticlockwise); } public static void main (String[] args) { String str1 = "Beginner" ; String str2 = "eksge" ; System.out.println(isRotated(str1, str2) ? "Yes" : "No" ); } } |
Python3
# Python code for the above approach # Python code to find if string is rotated by 2 positions def isRotated(str1, str2): n = len (str1) clockwise, anticlockwise = True , True # Check if str1 is rotated clockwise for i in range (n): if str1[i] ! = str2[(i + 2 ) % n]: clockwise = False break # Check if str1 is rotated anticlockwise for i in range (n): if str1[(i + 2 ) % n] ! = str2[i]: anticlockwise = False break # Return True if str1 is rotated by 2 positions either clockwise or anticlockwise return clockwise or anticlockwise # Driver code if __name__ = = "__main__" : str1 = "Beginner" str2 = "eksge" if isRotated(str1, str2): print ( "Yes" ) else : print ( "No" ) # This code is contributed by adityasharmadev01 |
C#
using System; public class GFG{ public static bool IsRotated( string str1, string str2) { int n = str1.Length; bool clockwise = true , anticlockwise = true ; // clockwise direction check for ( int i = 0; i < n; i++) { if (str1[i] != str2[(i + 2) % n]) { clockwise = false ; // not rotated clockwise break ; } } // anticlockwise direction check for ( int i = 0; i < n; i++) { if (str1[(i + 2) % n] != str2[i]) { anticlockwise = false ; // not rotated anticlockwise break ; } } return clockwise || anticlockwise; // if any of both is true, return true } public static void Main() { string str1 = "Beginner" ; string str2 = "eksge" ; Console.WriteLine(IsRotated(str1, str2) ? "Yes" : "No" ); } } |
Javascript
// JavaScript code to find if string is rotated by 2 positions function isRotated(str1, str2) { // clockwise direction check let n = str1.length; let clockwise = true , anticlockwise = true ; for (let i = 0; i < n; i++) { if (str1[i] != str2[(i + 2) % n]) { clockwise = false ; // not rotated clockwise break ; } } for (let i = 0; i < n; i++) { if (str1[(i + 2) % n] != str2[i]) { anticlockwise = false ; // not rotated anticlockwise break ; } } return clockwise || anticlockwise; // if any of both is true, return true } let str1 = "Beginner" ; let str2 = "eksge" ; isRotated(str1, str2) ? console.log( "Yes" ) : console.log( "No" ); |
Yes
Time Complexity – O(n), Iterating over the string 2 times for comparing both the strings.
Space Complexity – O(1)
Approach 3(using reverse function):
we can rotate the string one anticlock wise and then rotate the same string two times clockwise to get the answer.
algo:
- Reverse the first two characters of str1.
- Reverse the rest of the characters of str1.
- Reverse the entire string str1.
- Check if str1 is equal to str2. If true, return true; otherwise, proceed to the next step.
- Reverse the last two characters of str1.
- Reverse the rest of the characters except the last two of str1.
- Reverse the entire string str1.
- Check if str1 is equal to str2. If true, return true; otherwise, return false.
C++
// C++ code to find if string is rotated by 2 positions #include <iostream> using namespace std; bool isRotated(string str1, string str2) { reverse(str1.begin(), str1.begin() + 2); reverse(str1.begin() + 2, str1.end()); reverse(str1.begin(), str1.end()); if (str1 == str2) return true ; reverse(str1.end() - 2, str1.end()); reverse(str1.begin(), str1.end() - 2); reverse(str1.begin(), str1.end()); reverse(str1.end() - 2, str1.end()); reverse(str1.begin(), str1.end() - 2); reverse(str1.begin(), str1.end()); if (str1 == str2) return true ; return false ; } int main() { string str1 = "Beginner" ; string str2 = "eksge" ; isRotated(str1, str2) ? cout << "Yes" : cout << "No" ; return 0; } // this code is contributed by Prateek Kumar Singh |
Java
import java.util.Arrays; public class StringRotation { // Function to check if a string is rotated by 2 positions static boolean isRotated(String str1, String str2) { // Rotate the first string by 2 positions to the right str1 = rotateString(str1, 2 ); // Check if the rotated string is equal to the second string if (str1.equals(str2)) { return true ; } // Rotate the first string by 2 positions to the left str1 = rotateString(str1, - 2 ); // Check if the rotated string is equal to the second string return str1.equals(str2); } // Function to rotate a string by 'positions' positions static String rotateString(String str, int positions) { int length = str.length(); // Handle negative positions (rotate to the left) if (positions < 0 ) { positions = length + positions; } // Rotate the string by swapping characters char [] charArray = str.toCharArray(); reverse(charArray, 0 , positions - 1 ); reverse(charArray, positions, length - 1 ); reverse(charArray, 0 , length - 1 ); // Convert the character array back to a string return new String(charArray); } // Function to reverse a portion of the character array static void reverse( char [] charArray, int start, int end) { while (start < end) { char temp = charArray[start]; charArray[start] = charArray[end]; charArray[end] = temp; start++; end--; } } public static void main(String[] args) { String str1 = "Beginner" ; String str2 = "eksge" ; // Check if the string is rotated by 2 positions if (isRotated(str1, str2)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by shivamgupta0987654321 |
Python
def is_rotated(str1, str2): # Rotate the first string by 2 positions rotated_str1 = str1[ 2 :] + str1[: 2 ] # Check if the rotated string is equal to the second string if rotated_str1 = = str2: return True # Rotate the first string in the opposite direction by 2 positions rotated_str1 = str1[ - 2 :] + str1[: - 2 ] # Check if the rotated string is equal to the second string if rotated_str1 = = str2: return True # If neither rotation matches, return False return False # Main function def main(): str1 = "Beginner" str2 = "eksge" # Check if str1 is rotated by 2 positions to get str2 result = is_rotated(str1, str2) # Print the result print ( "Yes" if result else "No" ) # Execute the main function if __name__ = = "__main__" : main() |
C#
using System; class StringRotation { // Function to check if a string is rotated by 2 positions static bool IsRotated( string str1, string str2) { // Rotate the first string by 2 positions to the right str1 = RotateString(str1, 2); // Check if the rotated string is equal to the second string if (str1.Equals(str2)) { return true ; } // Rotate the first string by 2 positions to the left str1 = RotateString(str1, -2); // Check if the rotated string is equal to the second string return str1.Equals(str2); } // Function to rotate a string by 'positions' positions static string RotateString( string str, int positions) { int length = str.Length; // Handle negative positions (rotate to the left) if (positions < 0) { positions = length + positions; } // Rotate the string by swapping characters char [] charArray = str.ToCharArray(); Reverse(charArray, 0, positions - 1); Reverse(charArray, positions, length - 1); Reverse(charArray, 0, length - 1); // Convert the character array back to a string return new string (charArray); } // Function to reverse a portion of the character array static void Reverse( char [] charArray, int start, int end) { while (start < end) { char temp = charArray[start]; charArray[start] = charArray[end]; charArray[end] = temp; start++; end--; } } public static void Main() { string str1 = "Beginner" ; string str2 = "eksge" ; // Check if the string is rotated by 2 positions if (IsRotated(str1, str2)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
// Function to check if a string is rotated by 2 positions function isRotated(str1, str2) { // Rotate the first string by 2 positions to the right str1 = rotateString(str1, 2); // Check if the rotated string is equal to the second string if (str1 === str2) { return true ; } // Rotate the first string by 2 positions to the left str1 = rotateString(str1, -2); // Check if the rotated string is equal to the second string return str1 === str2; } // Function to rotate a string by 'positions' positions function rotateString(str, positions) { const length = str.length; // Handle negative positions (rotate to the left) if (positions < 0) { positions = length + positions; } // Rotate the string by swapping characters let charArray = str.split( '' ); reverse(charArray, 0, positions - 1); reverse(charArray, positions, length - 1); reverse(charArray, 0, length - 1); // Convert the character array back to a string return charArray.join( '' ); } // Function to reverse a portion of the character array function reverse(charArray, start, end) { while (start < end) { let temp = charArray[start]; charArray[start] = charArray[end]; charArray[end] = temp; start++; end--; } } // Main function function main() { let str1 = "Beginner" ; let str2 = "eksge" ; // Check if the string is rotated by 2 positions if (isRotated(str1, str2)) { console.log( "Yes" ); } else { console.log( "No" ); } } // Calling the main function main(); |
Time Complexity – O(n), Iterating over the string 2 times for comparing both the strings.
Space Complexity – O(1)
this approach is contributed by Prateek Kumar Singh (pkrsingh025)