String Rotation

A classic string problem that tests whether one string is a rotation of another, useful in cyclic data detection and sequence alignment tasks.

Problem

Given two strings s1 and s2, determine if s2 is a rotation of s1 using only one call to a substring check.

Example: s1 = "waterbottle", s2 = "erbottlewat", returns True.

Approach

The key insight: if you concatenate s1 with itself, every possible rotation of s1 appears as a contiguous substring. For "waterbottle", the doubled string "waterbottlewaterbottle" contains "erbottlewat" within it.

1. Verify both strings have equal length and are non-empty (a rotation can't change the length).
2. Concatenate s1 + s1.
3. Check if s2 is a substring of the result.

Implementation

def is_rotation(s1, s2):
    if len(s1) == len(s2) and len(s1) > 0:
        return s2 in (s1 + s1)
    return False

Complexity

• Time: O(n), string concatenation is O(n) and Python's in operator uses an optimized substring search.
• Space: O(n), for the concatenated string.

Takeaway

The concatenation trick is one of those clever reductions that makes a hard-sounding problem trivial. Worth remembering anytime you're checking cyclic equivalence.

---

Back to Algorithms & Data Structures