Rotate String — The Concatenation Trick [LC 796]

Problem Statement#

Given two strings s and goal, return true if and only if s can become goal after some number of shifts. A shift moves the leftmost character to the rightmost position.

Constraints:

• 1 <= s.length, goal.length <= 100
• s and goal consist of lowercase English letters

Input:  s = "abcde", goal = "cdeab"
Output: true

Input:  s = "abcde", goal = "abced"
Output: false

Why This Problem Matters#

LeetCode 796 is a popular screening question at Amazon and Google because it has a beautiful one-insight solution that distinguishes candidates who think creatively from those who reach for brute force. The concatenation trick — s + s contains all rotations of s as substrings — is a classic string insight that appears in circular buffer problems, DNA sequence analysis, and string period detection.

The problem also validates a useful interview skill: transforming a hard-seeming problem ("check all n rotations") into a trivial one ("substring check") via a clever reformulation.

The Core Insight#

Every rotation of s is a substring of s + s.

If s = "abcde", then s + s = "abcdeabcde". Check: "cdeab" appears at position 2 in "abcdeabcde" — yes! This rotation corresponds to rotating by 2 positions.

So the algorithm is:

1. Check len(s) == len(goal) (necessary condition)
2. Check goal in (s + s)

That's it. Python's in operator calls the built-in string matching (KMP or Boyer-Moore variant) which is O(n) on average.

Why does this work? Rotating s by k positions gives s[k:] + s[:k]. In s + s, this exact string starts at index k and has length n. So s + s contains every possible rotation of s as a contiguous substring.

Visual Dry Run#

s = "abcde", goal = "cdeab"

s + s = "abcdeabcde"
         0123456789

Sliding window of length 5 (= len(s)):

• Position 0: "abcde" ≠ "cdeab"
• Position 1: "bcdea" ≠ "cdeab"
• Position 2: "cdeab" = "cdeab" — FOUND!

Return true.

Solution (Optimal)#

class Solution:
    def rotateString(self, s, goal):
        return len(s) == len(goal) and goal in s + s

var rotateString = function(s, goal) {
    return s.length === goal.length && (s + s).includes(goal);
};

Time: O(n) — string concatenation O(n), substring search O(n) average Space: O(n) — s + s creates a string of length 2n

Common Mistakes#

• Missing the length check — goal in s + s could return true for different-length strings (e.g., if goal is shorter and appears as substring)
• Checking all n rotations in a loop — O(n²) and unnecessary given the concatenation trick
• Using s + s comparison without checking if goal length matches — "abcde" contains "cde" but "cde" is not a rotation
• Forgetting 0 rotations is valid — if s == goal, it's a rotation by 0 and should return true (handled by goal in s + s)
• Implementing custom KMP for this — unnecessary for the problem size (n ≤ 100) and the interview context

Interview Tips#

• State the insight immediately: "every rotation of s appears as a substring of s+s"
• Explain why in one sentence: "rotating by k gives s[k:]+s[:k], which is exactly the window starting at index k in s+s"
• Mention the length guard: "we need len(s)==len(goal) to prevent false positives from shorter substrings"
• Note that the 0-rotation case (s==goal) is automatically handled — goal appears at position 0 in s+s
• Compare brute force O(n²) with this O(n) approach to demonstrate the value of the insight

Follow-up Questions#

• Can you solve this without string concatenation? (Yes — binary search or compare character by character at each rotation, O(n²))
• What is the most efficient string matching algorithm? (KMP or Rabin-Karp — O(n) worst case for pattern in text)
• How does this relate to string period detection? (A string with period p satisfies s = (s+s)[:n] for rotation p — related but different)
• What if you want to find the minimum rotation to transform s into goal? (Find the index where goal appears in s+s — that's the rotation count)
• What if characters are case-sensitive or include special characters? (No change — the algorithm works for any character set)

Key Takeaways#

• LeetCode 796 is asked at Amazon and Google — the concatenation trick is the key insight
• Every rotation of s is a substring of s+s — elegant one-line solution
• Always check len(s) == len(goal) first — prevents false positives from shorter goals being substrings
• The 0-rotation case (s == goal) is handled automatically — goal at position 0 in s+s
• Time O(n), Space O(n) — building and searching s+s
• This insight appears in circular buffer matching, DNA sequence rotation, and string period problems
• In Python: return len(s) == len(goal) and goal in s + s — the cleanest single-line solution in competitive programming