303. Rotate String

A rotation of s is just s[k:] + s[:k] for some k. There are at most n distinct rotations, so we can try them all and check if any equals goal.

Approach

1. If lengths differ, return False immediately.
2. For each k from 0 to n - 1, build s[k:] + s[:k] and compare with goal.
3. If any rotation matches, return True. Otherwise False.

Complexity

• Time: O(n²) — n rotations, each compared in O(n).
• Space: O(n) — temporary rotated string.

import java.util.*;

class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        for (int k = 0; k < s.length(); k++) {
            if ((s.substring(k) + s.substring(0, k)).equals(goal)) return true;
        }
        return false;
    }
}

Every rotation of s appears as a contiguous substring of s + s. So goal is a rotation of s iff goal is a substring of s + s (and the lengths match).

The key observation

If s = "abcde", then concatenating s with itself gives:

s + s = "abcdeabcde"

Look at every length-5 window inside that doubled string:

Those are exactly the five rotations of s. So checking whether goal is a rotation of s is the same as checking whether goal appears as a substring of s + s.

Steps

1. If len(s) != len(goal), return False immediately — strings of different lengths can never be rotations of each other.
2. Build the doubled string s + s.
3. Return goal in s + s — Python's in operator runs a linear-time substring search.

Walk-through

• s = "abcde", goal = "cdeab" → s + s = "abcdeabcde". "cdeab" starts at index 2. → True.
• s = "abcde", goal = "abced" → s + s = "abcdeabcde". "abced" is nowhere inside. → False.
• s = "aa", goal = "a" → lengths differ. → False immediately.

Why we need the length check

Without it, s = "aa" and goal = "a" would return True because "a" is a substring of "aaaa". The length guard removes that false positive.

Complexity

• Time: O(n) — the in operator on Python strings uses an efficient string-search algorithm.
• Space: O(n) — the doubled string.