Rotate String: The Concatenation Trick

LeetCode Rotate String (problem 796) asks you to determine whether one string is a rotation of another. Given two strings s and goal, return true if goal can be obtained by performing some number of left rotations on s. A single left rotation moves the first character to the end: "abcde" becomes "bcdea".

The problem

Given strings s and goal, return true if and only if s can become goal after some number of shifts.

Why this problem matters

Rotate String is a clean example of how reframing a problem unlocks a much simpler solution. The brute-force approach works, but it misses a beautiful structural insight about cyclic strings. That insight, the concatenation trick, shows up repeatedly in string problems involving rotations, periodicity, and pattern matching. Once you internalize it, you will reach for it instinctively whenever a problem involves cyclic shifts.

The brute force approach

The most direct way to solve this is to try all possible rotations. For a string of length n, there are exactly n distinct rotations. You can generate each one by slicing the string at every position and checking if the result matches goal.

def rotate_string_brute(s, goal):
    if len(s) != len(goal):
        return False
    for i in range(len(s)):
        if s[i:] + s[:i] == goal:
            return True
    return False

This works, but each comparison takes O(n) time, and you do it up to n times, giving O(n^2) overall. You can do better.

The key insight

Here is the core idea: every rotation of a string s appears as a contiguous substring inside s + s.

Think about it. When you concatenate s with itself, you create a string that contains every possible cyclic arrangement. If s = "abcde", then s + s = "abcdeabcde". Look at the substrings of length 5 starting at each position:

• Index 0: "abcde" (rotation by 0)
• Index 1: "bcdea" (rotation by 1)
• Index 2: "cdeab" (rotation by 2)
• Index 3: "deabc" (rotation by 3)
• Index 4: "eabcd" (rotation by 4)

Every single rotation is in there. So checking whether goal is a rotation of s reduces to checking whether goal is a substring of s + s. You just need to verify that the lengths match first, because a shorter or longer string sitting inside s + s would not be a valid rotation.

The code

def rotate_string(s, goal):
    return len(s) == len(goal) and goal in s + s

That is the entire solution. One line. The length check ensures you do not get false positives from substrings that happen to match but have the wrong length. The in operator handles the substring search.

Visual walkthrough

Walk through the algorithm step by step with s = "abcde" and goal = "cdeab".

The match at index 2 confirms that "cdeab" is a valid rotation of "abcde". If you tried goal = "cdeba" instead, the substring search would fail and the function would return false.

Complexity analysis

Python's in operator uses a fast substring search algorithm (a variant of Boyer-Moore-Horspool) that runs in O(n) on average. The concatenated string has length 2n, so the search operates on that. In the worst case, substring search can degrade to O(n^2), but this is rare with typical inputs. If you need guaranteed linear time, you can use the KMP algorithm for the substring check. The space cost comes from building the 2n-length concatenated string.

Building blocks

String concatenation as a rotation detector

The trick of doubling a string to expose all its rotations is one of the most reusable patterns in string manipulation. It works because concatenation creates a "sliding window" over all cyclic shifts. You will see this same idea in problems like Repeated Substring Pattern, where the doubled string reveals periodicity rather than rotation.

Substring search as the workhorse

The in operator (or find, indexOf, or strstr in other languages) does all the work. Understanding that substring search is a well-optimized primitive in most languages lets you write concise solutions without worrying about reimplementing search logic. In an interview, you might be asked what algorithm runs under the hood, so it helps to know about KMP, Rabin-Karp, or Boyer-Moore.

Edge cases

• Empty strings. If both s and goal are empty, the answer is true. The length check passes (both are 0), and an empty string is trivially a substring of any string.
• s equals goal. When s and goal are identical, the answer is true. This corresponds to a rotation by 0 positions. The concatenation s + s always contains s at index 0.
• Single character. s = "a" and goal = "a" returns true. s = "a" and goal = "b" returns false. The length check passes, but "b" is not found in "aa".
• Different lengths. If len(s) != len(goal), the answer is always false. The length check short-circuits before you even build the concatenated string.
• Same characters, different order. s = "abc" and goal = "bca" returns true (valid rotation), but s = "abc" and goal = "bac" returns false (not a rotation, just a permutation).

From understanding to recall

This problem has one of the highest "insight-to-code" ratios you will encounter. The solution is a single line, but arriving at that line requires the non-obvious leap of thinking about s + s. That is exactly the kind of pattern that slips away under interview pressure if you have not practiced it.

Write the one-liner from memory. Then write the brute-force version. Compare them. Understand why both are correct and when you would prefer one over the other. Then space out your reviews so the concatenation trick becomes automatic the moment you see anything involving rotations.

Related posts

• Repeated Substring Pattern
• Reverse String
• String Compression