POTD Solutions | 12 Nov’ 23 | Check if string is rotated by two places
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 Strings but will also help you build up problem-solving skills.
POTD 12 November: Check if string is rotated by two places:
Given two strings a and b. The task is to find if the string ‘b’ can be obtained by rotating (in any direction) string ‘a’ by exactly 2 places.
Examples:
Input: string1 = amazon, string2 = azonam
Output: Yes
Explanation: amazon can be rotated anti-clockwise by two places, which will make it as azonam.Input: string1 = w3wiki, string2 = BeginnerBeginnerfor
Output: No
Explanation: If we rotate w3wiki by two place in any direction, we won’t get BeginnerBeginnerfor.
Check if string is rotated by two places by rotating string Clockwise and Anti-clockwise:
The idea is to Rotate the String1 in both clockwise and ant-clockwise directions once. And then check if this rotated string is equal to String2.
Step-by-step approach:
- If the length of both the strings are not equal or they are less than 2, return false.
- Store anti-clockwise rotation of string by concatenating substring of size two from end to the starting of the string.
- Store clockwise rotation of string by concatenating substring of size two from beginning to the end of the string.
- Checking if any of them is equal to string, return true.
Below is the implementation of the above approach:
C++
class Solution { public : // Function to check if a string can be obtained by // rotating another string by exactly 2 places. bool isRotated(string str1, string str2) { if (str1.length() != str2.length()) return false ; if (str1.length() <= 2 || str2.length() <= 2) return (str1 == str2); string clock_rot = "" ; string anticlock_rot = "" ; int len = str2.length(); // storing anti-clockwise rotation of string by // concatenating substring of size two from end to // the starting of the string. anticlock_rot = anticlock_rot + str2.substr(len - 2, 2) + str2.substr(0, len - 2); // storing clockwise rotation of string by // concatenating substring of size two from beginning // to the end of the string. clock_rot = clock_rot + str2.substr(2) + str2.substr(0, 2); // checking if any of them is equal to string, we // return true. return (str1.compare(clock_rot) == 0 || str1.compare(anticlock_rot) == 0); } }; |
Java
class Solution { //Function to check if a string can be obtained by rotating //another string by exactly 2 places. public static boolean isRotated(String str1, String str2) { if (str1.length() <= 2 || str2.length() <= 2 ) if (str1.equals(str2)) return true ; else return false ; if (str1.length() != str2.length()) return false ; int bt = 0 ; char temp,temp1; int flag = 0 ; char c1[] = str1.toCharArray(); char c2[] = str2.toCharArray(); char ck[] = new char [c1.length]; char ak[] = new char [c1.length]; //storing anti-clockwise rotation of string by concatenating //substring of size two from end to the starting of the string. for ( int a= 0 ; a<c1.length- 2 ; a++){ ck[a] = c1[a+ 2 ]; } ck[c1.length- 2 ] = c1[ 0 ]; ck[c1.length- 1 ] = c1[ 1 ]; //storing clockwise rotation of string by concatenating substring //of size two from beginning to the end of the string. for ( int a= 2 ; a<c1.length; a++){ ak[a] = c1[a- 2 ]; } ak[ 0 ] = c1[c1.length- 2 ]; ak[ 1 ] = c1[c1.length- 1 ]; //checking if any of them is equal to string, we return true. for ( int a= 0 ; a<c1.length; a++){ if (ck[a]!=c2[a]&&ak[a]!=c2[a]){ flag = 1 ; break ; } } if (flag == 0 ){ bt = 1 ; } flag = 0 ; if (bt == 1 ) return true ; else return false ; } } |
Python3
class Solution: #Function to check if a string can be obtained by rotating #another string by exactly 2 places. def isRotated( self ,str1,str2): n = len (str2) if (n< 3 ): return str1 = = str2 #storing anti-clockwise rotation of string by concatenating #substring of size two from end to the starting of the string. anticlock_str = str2[ 2 :] + str2[ 0 : 2 ] #storing clockwise rotation of string by concatenating substring #of size two from beginning to the end of the string. clockwise_str = str2[ - 2 ] + str2[ - 1 ] + str2[:n - 2 ] #checking if any of them is equal to string, we return true. if (str1 = = anticlock_str or str1 = = clockwise_str): return True return False |
Time Complexity: O(N), Time is taken to rotate the string and then compare the string, where N is the length of the strings.
Auxiliary Space: O(N), Space for storing clockwise and anticlockwise strings.
Check if string is rotated by two places without using Auxiliary Space:
The idea is to check directly if the string is rotated or not by comparing the two strings.
Step-by-step approach:
- Compare for clockwise and anticlockwise rotation by using for loops and the modulo operator:
- for clockwise direction,
- Run a loop from i = 0 to i < N
- if str1[i] != str2[(i + 2) % N], then update the variable clockwise as false and break the loop.
- Run a loop from i = 0 to i < N
- For anti clockwise direction
- Run another loop from 0 to i < N
- if str1[i+2] % N != str2[i], then update the variable anticlockwise as false and break the loop.
- Run another loop from 0 to i < N
- for clockwise direction,
- Return clockwise | anticlockwise (if any of them is true, it gives us as true result)
Below is the implementation of the above approach:
C++
class Solution { public : // Function to check if a string can be obtained by // rotating another string by exactly 2 places. bool isRotated(string str1, string str2) { // Your code here 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 } }; |
Java
public class Solution { // Function to check if a string can be obtained by // rotating another string by exactly 2 places. public boolean isRotated(String str1, String str2) { // Your code here int n = str1.length(); boolean clockwise = true , anticlockwise = true ; // Check if str2 is obtained by rotating str1 // clockwise by 2 places for ( int i = 0 ; i < n; i++) { if (str1.charAt(i) != str2.charAt((i + 2 ) % n)) { clockwise = false ; // not rotated clockwise break ; } } // Check if str2 is obtained by rotating str1 // anticlockwise by 2 places for ( int i = 0 ; i < n; i++) { if (str1.charAt((i + 2 ) % n) != str2.charAt(i)) { anticlockwise = false ; // not rotated anticlockwise break ; } } // If either clockwise or anticlockwise rotation is // true, return true return clockwise || anticlockwise; } } |
Python3
class Solution: # Function to check if a string can be obtained by rotating # another string by exactly 2 places. def isRotated( self , str1: str , str2: str ) - > bool : # Your code here n = len (str1) clockwise, anticlockwise = True , True # Check if str2 is obtained by rotating str1 clockwise by 2 places for i in range (n): if str1[i] ! = str2[(i + 2 ) % n]: clockwise = False # not rotated clockwise break # Check if str2 is obtained by rotating str1 anticlockwise by 2 places for i in range (n): if str1[(i + 2 ) % n] ! = str2[i]: anticlockwise = False # not rotated anticlockwise break # If either clockwise or anticlockwise rotation is true, return true return clockwise or anticlockwise |
Time Complexity: O(N), Iterating over the string 2 times for comparing both the strings, where N is the length of the strings.
Auxiliary Space: O(1)