796. Rotate String

String
String Matching

TIME

O(n)

SPACE

O(n)

Intuition

Every rotation of s appears inside s + s. For example, if s = "abcde", then s + s = "abcdeabcde", which contains rotations like "bcdea" and "cdeab".

So the problem becomes string matching: check whether goal appears in s + s. To make the O(n) time guarantee explicit, use KMP instead of relying on a built-in substring search.

Approach

If the lengths are different, return false.
Build text = s + s.
Build the KMP lps array for goal.
- lps[i] stores the length of the longest proper prefix of goal[0..i] that is also a suffix.
Scan text with KMP.
- When characters match, advance the match length.
- When they do not match, fall back using the lps array instead of restarting from scratch.
If the full goal string is matched, return true.
Otherwise, return false.

Complexity

Time: O(n), build lps in O(n), then scan s + s in O(2n)
Space: O(n), the doubled string and lps array use extra space

Edge Cases

Different lengths → impossible to rotate into each other
Same string → zero shifts are allowed, so return true
Repeated characters → substring check still covers all rotations

Code

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        """
        796. Rotate String
        Time: O(n)
        Space: O(n)
        """
        if len(s) != len(goal):
            return False

        pattern = goal
        text = s + s
        lps = self._build_lps(pattern)
        matched = 0

        for char in text:
            while matched > 0 and char != pattern[matched]:
                matched = lps[matched - 1]

            if char == pattern[matched]:
                matched += 1

            if matched == len(pattern):
                return True

        return False

    def _build_lps(self, pattern: str) -> list[int]:
        lps = [0] * len(pattern)
        length = 0

        for i in range(1, len(pattern)):
            while length > 0 and pattern[i] != pattern[length]:
                length = lps[length - 1]

            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length

        return lps

/**
 * 796. Rotate String
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }

        String text = s + s;
        int[] lps = buildLps(goal);
        int matched = 0;

        for (int i = 0; i < text.length(); i++) {
            while (matched > 0 && text.charAt(i) != goal.charAt(matched)) {
                matched = lps[matched - 1];
            }

            if (text.charAt(i) == goal.charAt(matched)) {
                matched++;
            }

            if (matched == goal.length()) {
                return true;
            }
        }

        return false;
    }

    private int[] buildLps(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0;

        for (int i = 1; i < pattern.length(); i++) {
            while (length > 0 && pattern.charAt(i) != pattern.charAt(length)) {
                length = lps[length - 1];
            }

            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
            }
        }

        return lps;
    }
}