796. Rotate String

Problem¶

Given two strings s and goal, return whether goal is some left-rotation of s.

• Shift = move the first char of s to the end.
• Strings must have the same length.

Example:

s="abcde", goal="cdeab" -> True
because: abcde -> bcdea -> cdeab

Key trick¶

A string rotation must appear inside s + s.

• If len(s) != len(goal), answer is False.
• Otherwise, goal in (s + s) is exactly the rotation check.

Trap¶

• Forgetting to check equal lengths first.
• Rebuilding every rotation one by one when a simpler check exists.
• Missing edge cases like identical strings, where zero shifts is allowed.

Why is it interesting?¶

It tests whether you can turn a simulation problem into a string property.

• Naive idea: try all rotations.
• Better idea: use the doubled-string observation.

Python solution¶

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        # Rotations preserve length.
        if len(s) != len(goal):
            return False

        # Every rotation of s appears as a substring of s + s.
        return goal in (s + s)

Comment on my solution¶

Your solution is correct and interview-safe.

• Good:

  • Handles length mismatch.
  • Easy to understand.
  • Correctly allows zero shifts when s == goal.

• Can be improved:

  • It is \(O(n^2)\) in the worst case because it builds up to n rotated strings of length n.
  • The standard interview trick is shorter and cleaner:

return len(s) == len(goal) and goal in (s + s)

• One note:
  • Under LeetCode constraints, your version is still fast enough.

# OK - pass leetcode tests
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        for i in range(len(s)):
            s_transposed = s[i:] + s[:i]
            if s_transposed == goal:
                return True
        return False