String Rotation Coding Interview: The Two-Line Solution Most Miss

Stop. Try this before reading another line. Thirty seconds, no hints.

Given two strings s1 and s2, determine whether s2 is a rotation of s1. Example: "erbottlewat" is a rotation of "waterbottle".

Write down your approach. This is a classic string rotation coding interview problem (LeetCode 796 if you want to drill it). The optimal solution is two lines.

What Your Brain Reaches For (And Why It Betrays You)

Most candidates start generating rotations.

def is_rotation_brute(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    for i in range(len(s1)):
        if s1[i:] + s1[:i] == s2:
            return True
    return False

This works. It is O(n²) time, and the math is worth being precise about: the loop runs n times, each iteration builds s1[i:] + s1[:i] (two slices plus a concatenation, all O(n)) and compares it against s2 (O(n)). So every iteration is Θ(n) and the total is Θ(n²). Space is O(n) for the temporary string built each pass.

It is also the kind of code that makes your interviewer scribble "brute force" in their notes while smiling politely at you.

Some candidates go further and reach for KMP, suffix arrays, or rolling hashes. These are genuinely good tools. You do not need any of them to get to the right answer here. (One of them is the right follow-up answer. Keep reading.)

A very patient interviewer watching a candidate spend 30 minutes on a "simple" problem

Your interviewer. Right now. While you debug your third nested loop.

The Two-Line String Rotation Solution

If s2 is a rotation of s1, then s2 appears as a substring of s1 + s1.

def is_rotation(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    return s2 in s1 + s1

Two lines. Why does it work? Doubling s1 produces a string that contains every possible rotation as a contiguous substring:

s1  + s1  = w a t e r b o t t l e w a t e r b o t t l e
                       ^                   ^
                       erbottlewat starts here

Scan the doubled string and "erbottlewat" is right there. So is "bottlewater". So is every rotation of "waterbottle". The length guard rules out the degenerate case where s2 is the same letters in a different multiset (e.g. "wateroottle" would never appear as a substring, but a shorter or longer string would falsely match without the check).

Why `in` Is O(n), Not O(n·m)

Saying "the in operator does a substring search" is fine until your interviewer asks the obvious follow-up: what is its time complexity? You should be able to answer without hand-waving.

CPython implements str.__contains__ in Objects/stringlib/fastsearch.h. For sufficiently long patterns, it uses Crochemore and Perrin's two-way algorithm, which has O(n) worst-case time and O(log m) extra space. For short patterns and small alphabets, it falls back to a Boyer-Moore-Horspool variant with a Bloom-filter shortcut. The same two-way algorithm backs glibc and musl's strstr and memmem, so the cost model is the same in C if you ever rewrite this.

So s2 in s1 + s1 is:

s1 + s1: O(n) time and O(n) space to build the doubled string
The two-way search: O(n) worst case, sublinear best case

Total: O(n) time, O(n) extra space.

The naive O(n·m) upper bound you see thrown around for substring search is correct for the textbook double-loop. It is wrong for CPython, glibc, musl, Java's String.indexOf (which uses naive search but with the short patterns this problem hands it), and most modern stdlibs.

Why You Missed It (Don't Worry, Everyone Does)

The word "rotation" fired a neuron. That neuron said "generate candidates." You opened your mental toolbox labeled STRINGS, grabbed the first thing that looked useful, and started looping. Pattern recognition is supposed to help you in interviews. Here it mugged you.

The step most candidates skip: ask what a rotated string looks like in relation to the original.

A rotation is a split and reattach. Cut the original somewhere, swap the two halves, glue them back. Write two copies of the original back to back and every possible cut point appears in the middle as a substring. That is not a trick. That is what the definition looks like if you draw it out.

When your approach requires a loop that generates candidates to compare against, pause. Ask: is there a transformation that makes the search trivial?

For rotation: instead of "which rotation of s1 matches s2?", ask "where does s2 appear if I write s1 twice?" One question leads to a loop. The other leads to a single substring check.

This reframe is the gap between the candidate who writes twenty lines and the one who writes two. Both might get the right answer. Only one signals efficient thinking.

If you catch that your approach is O(n²) mid-interview, say so out loud. Then ask whether a smarter observation exists before you start optimizing the brute force. That pause, narrated, is worth more than silently burning five minutes on an over-engineered loop. (More on what to do when you are blanking: stuck in a coding interview and coding interview hints.)

The Follow-Up Questions (The Interviewer Isn't Done With You)

A good interviewer won't stop at the solution. Expect:

What is the time and space complexity? (O(n) time, O(n) space for the concatenated string)
Can you do it without allocating s1 + s1?
What changes if the strings contain Unicode?

The first one you have covered above. Let's do the other two.

Saving the O(n) space: modular indexing

The doubled string is convenient, not necessary. You can search the conceptual s1 + s1 directly by treating its index j as s1[j % n]. That keeps space at O(1) beyond the inputs:

def is_rotation_no_alloc(s1: str, s2: str) -> bool:
    n = len(s1)
    if n != len(s2):
        return False
    if n == 0:
        return True
    for start in range(n):
        if all(s1[(start + k) % n] == s2[k] for k in range(n)):
            return True
    return False

This is the standard naive substring search, just over a virtual buffer. Worst-case time is back to O(n·m) which here is O(n²), but the extra space is O(1). It is the right answer when memory is the constraint and the strings are small.

Getting O(n) time AND O(1) extra space: KMP on the virtual doubled string

Here is the follow-up an interviewer will ask if you propose modular indexing: can you keep O(n) time and avoid the doubled string? Yes. Run KMP with s2 as the pattern over the virtual text s1[i % n]. KMP's failure table is O(m) preprocessing on the pattern, and the search itself is O(n). The virtual text never gets materialized, so the only extra space is the O(m) failure table.

def is_rotation_kmp(s1: str, s2: str) -> bool:
    n = len(s1)
    if n != len(s2):
        return False
    if n == 0:
        return True

    fail = [0] * n
    k = 0
    for i in range(1, n):
        while k > 0 and s2[k] != s2[i]:
            k = fail[k - 1]
        if s2[k] == s2[i]:
            k += 1
        fail[i] = k

    k = 0
    for i in range(2 * n):
        c = s1[i % n]
        while k > 0 and s2[k] != c:
            k = fail[k - 1]
        if s2[k] == c:
            k += 1
        if k == n:
            return True
    return False

Total: O(n) time, O(n) auxiliary for the failure table, no doubled input string. Strictly speaking that is not "O(1) extra," but it is the lower bound for any linear-time approach that does not assume hashing. This is the answer that lands.

A purist alternative is to skip KMP entirely and use Rabin-Karp rolling hashes on the virtual doubled buffer. Same time bound on average, smaller constants in practice, but with collision risk you have to acknowledge. Pick one and explain why.

The Unicode question

In Python 3, strings are sequences of Unicode code points, not bytes. PEP 393 stores them as 1, 2, or 4 bytes per code point depending on the largest one present, and indexing remains O(1) regardless. So s2 in s1 + s1 does the right thing for "café", "日本語", and emoji that fit in a single code point.

The one trap: characters that are made of multiple code points (combining marks, skin-tone modifiers, country flags) compare code point by code point. "é" and "é" look identical and are different strings. If the spec says "Unicode-aware rotation," normalize first with unicodedata.normalize("NFC", s) before doubling and searching. That is a one-sentence aside that lands well; the interviewer wants to know you noticed, not that you can recite the Unicode standard.

In C or C++, the same code does not just work. std::string::find operates on char (one byte) and is encoding-blind. "é" encoded as UTF-8 is two bytes; if you split mid-character you still get a successful byte-level substring match, which is a real bug if the strings are user input. The fix is either to convert to std::u32string (one code unit per code point) or to use ICU. Knowing this difference, and mentioning it without being asked, is the kind of signal that sticks in a write-up.

A Cheat Sheet

Approach	Time	Extra space	When to mention
Generate every rotation, compare	O(n²)	O(n)	Brute force / sanity check
`s2 in s1 + s1`	O(n) avg, O(n) worst (CPython two-way)	O(n) for the doubled string	Default answer
Modular indexing + naive search	O(n²) worst	O(1)	When memory is the constraint
KMP on virtual doubled string	O(n)	O(m) failure table	When asked for "O(n) without allocating `s1+s1`"
Rabin-Karp on virtual doubled string	O(n) avg	O(1) (ignoring hash)	When you want hash trade-offs to discuss

Notice that the answers stratify by what the interviewer optimizes for: clarity, time, space, or pure asymptotic purity. Pick the one that matches the constraint they actually stated.

Where the Pattern Generalizes

The "double the structure and search inside" idea shows up more than you would expect:

Checking circular subarrays in problems like maximum sum circular subarray (double the array, use a sliding window).
Detecting cycles in a string of moves (concatenate the move list with itself and look for net-zero substrings).
Necklace and bracelet counting in combinatorics, where rotations are equivalence classes.

The pattern is: when a problem has wraparound, materialize the wraparound and the problem reduces to a normal scan. Sometimes you materialize it for real, sometimes virtually with a modular index. Both are valid.