Program to check whether a string is a rotation of another in Python

January 11, 2022

What is string rotation and how to check for string rotations in two given strings?

Imagine a string with it’s last element pointing to the first element of the string. Now when you iterate through that string with a window on, that of the size of that of the string. As we move the window over the string, we see that every step we go forward, the first element of the window is removed from the front and added at the end. This whole process is called string rotations and the window strings produced are the rotations of the original string.

We can check for valid rotations by concatenating the original string to itself creating a string twice the length. Now we use the rotation string a the window and parse through the concatenated string, if the pattern matches, it’s valid rotation, otherwise it isn’t. 

Checking for Valid String Rotation in Python

Checking for Valid String Rotations in Python

The task is to check for valid string rotation. The approach is to concatenate the original string with itself forming a new string. Now if the string rotation is valid, the rotated string must be present in the concatenated new string. If the rotated string is not present in the concatenated string, it’s not a valid rotation. For instance,

In the figure adjacent, we have two strings string1 and string2. string1 is “12341” and string2 is “41123”. To check for valid string rotations we concatenate the original string, which is string1, with itself. Now we try and trace “41123” in the concatenated string. As it’s visible, the string2 i.e the rotated string is a substring of the concatenated string. Therefore, string2 is a valid rotation of the original string i.e string1.

Checking for Valid String Rotation in Python

Program to check for string rotation in python

Python Code

string1 = input()
string2 = input()
if len(string1)!= len(string2):
  print('Invalid rotation')
else:
  newstrn = string1+string2
  if string2 in newstrn:
    print('Valid Rotation')
  else:
    print('Invalid Rotation')

Output

abcd
dabc
Valid Rotation

Explanation

In the above code, we have two inputs, string1 is the rotated string whereas string2 is the original string. Our task is to check whether string1 is a valid rotation of all the characters in string2.

The algorithm for the above code is as follows:

  1. Take string1 and string2 as inputs using the input() function.
  2. check if string1 and string2 are of equal lengths, if false, print “Invalid rotation”.
  3. Else, append the concatenation of string1 and string2 in a newstr string variable.
  4. check if string2 is in newstr string variable.
  5. if true print “Valid Rotation”. Else, print “Invalid Rotation”.

The output of the above code is a string saying “Valid Rotation’ if true or “Invalid Rotation” otherwise.

For more solutions to the same question, click the button.

C Code