Rotate String

Rotate String

What is this problem about?

The Rotate String interview question asks you to determine whether a string s can become another string goal after some number of left-rotations. A left rotation moves the first character to the end. For example, "abcde" rotated twice gives "cdeab". Return true if goal is achievable by rotating s any number of times (including 0).

Why is this asked in interviews?

This problem is asked at Apple, Microsoft, Meta, Amazon, Oracle, Google, Bloomberg, and Adobe because it tests string matching insight. A naive approach simulates all rotations (O(n^2)); the elegant solution uses the string doubling trick: goal is a rotation of s if and only if goal is a substring of s + s (and len(s) == len(goal)). This connects to KMP and suffix automaton thinking.

Algorithmic pattern used

The pattern is string doubling with substring containment check. The key insight: all possible rotations of s appear as substrings of s + s. So check: len(s) == len(goal) and goal in (s + s). Python's in operator performs O(n) average substring search. For optimal O(n) guarantee, use KMP. This is the string matching interview pattern applied to rotations.

Example explanation

s = "abcde", goal = "cdeab".

len(s) = len(goal) = 5. ✓

s + s = "abcdeabcde". Does "cdeab" appear? Check: ..."cdeab"... yes, at index 2. Return true.

s = "abc", goal = "bca": s + s = "abcabc". "bca" appears at index 1. Return true.

s = "abc", goal = "acb": s + s = "abcabc". "acb" does not appear. Return false.

Common mistakes candidates make

• Forgetting to check len(s) == len(goal) before the substring check — "ab" is a substring of "abab" but "ab" is not a valid rotation of "aba".
• Simulating all n rotations explicitly — O(n^2) and unnecessary.
• Assuming left rotation when the problem's rotation direction doesn't matter (any rotation works both ways).
• Handling s = "" separately — if both are empty, return true.

Interview preparation tip

For the Rotate String coding problem, the string matching interview pattern with the doubling trick is the clean O(n) solution. goal in (s + s) is the entire algorithm body. Google and Adobe interviewers appreciate when you explain WHY this works — all n rotations of s appear exactly once as length-n substrings of s+s. This one-insight, one-liner problem is a great opportunity to demonstrate mathematical elegance over brute force.