Check if Strings are Rotations

Check if Strings are Rotations asks a deceptively simple question: can you spin one string around to get another? The clever one-line answer hinges on a single observation about where rotations live — and it turns a fiddly index-juggling problem into a plain substring search.

The slow way first

The brute-force idea: generate every rotation of s1 and check each one against s2. For a string of length n there are n rotations, and building plus comparing each one costs O(n), so the whole thing is O(n²). It works, but it is clumsy — lots of slicing and a loop you do not really need.

The question to ask: is there one string that already contains all of those rotations at once? If so, the whole problem collapses into a single lookup.

The idea: every rotation hides in s1 + s1

Here is the trick. Glue a second copy of s1 onto the end of itself to get doubled = s1 + s1. For s1 = "ABCD" that is "ABCDABCD". Now slide a window of length n across it:

ABCD · BCDA · CDAB · DABC

Those are exactly the four rotations of "ABCD". So s2 is a rotation of s1 if and only if the lengths match and s2 appears as a substring of s1 + s1.

Always check the lengths first. If s1 and s2 are different sizes, s2 can never be a rotation, and the substring test alone would wrongly accept a shorter s2.

Walk through it

Step through the animation. First we confirm both strings have length 4. Then we build the doubled string "ABCDABCD" and slide a search window j across it. At offset 0 the window is "ABCD", at offset 1 it is "BCDA" — neither matches. At offset 2 the window reads "CDAB", which is exactly s2, so we stop and return True.

Pseudocode

if length of s1 != length of s2:
    return False                 # different sizes can never be rotations
if s1 is empty:
    return True                  # two empty strings are rotations of each other
doubled = s1 + s1                # contains every rotation of s1 as a window
return (s2 is a substring of doubled)

The Python solution

def is_rotation(s1, s2):
    if len(s1) != len(s2):
        return False
    if not s1:
        return True
    doubled = s1 + s1
    return s2 in doubled

• Line 2 is the length guard: unequal lengths rule out a rotation immediately and protect the substring test.
• Line 4 handles the empty-string edge case so "" and "" correctly return True.
• Line 6 builds doubled = s1 + s1, the string that holds every rotation of s1 as a length-n window.
• Line 7 is the whole algorithm: s2 in doubled is a single substring search. If s2 shows up anywhere inside, it is a rotation.

Complexity

Building s1 + s1 costs O(n) extra space, and Python's substring search runs in linear time on average. We trade a little memory to turn an O(n²) loop into a one-line O(n) check.

When this pattern shows up

Practice