796. Rotate String

Reformulated question¶

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 this question 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.

Solve the problem with idiomatic python¶

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)

Alternative with the same idea is unnecessary here because Python already gives the cleanest exact solution.

Pytest test¶

import pytest


@pytest.mark.parametrize(
    ("s", "goal", "expected"),
    [
        ("abcde", "cdeab", True),
        ("abcde", "abced", False),
        ("aa", "aa", True),
        ("", "", True),
        ("a", "a", True),
        ("ab", "ba", True),
        ("ab", "ab", True),
        ("abc", "cab", True),
        ("abc", "acb", False),
        ("waterbottle", "erbottlewat", True),
        ("abc", "abcd", False),
    ],
)
def test_rotate_string(s, goal, expected):
    assert Solution().rotateString(s, goal) is expected

Comment 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