Rotate String
Understanding the Problem
We need to determine if one string is a rotation of another. A rotation means taking some number of characters from the front of the string and moving them to the back. For example, "cdeab" is a rotation of "abcde" because the first two characters ("ab") moved to the end.
If s and goal have different lengths, the answer is false. A string cannot rotate into a string of a different length, so this is an early exit before any real work.
The question that remains: given two strings of the same length, how do we check whether one is a rotation of the other?
Key Constraints:
1 <= s.length, goal.length <= 100: With n capped at 100, even an O(n^2) scan over every rotation runs in at most 10,000 character comparisons. Runtime is not the concern here; the approaches differ mainly in how much extra memory they allocate and how cleanly they express the rotation idea.sandgoalconsist of lowercase English letters. There are no special characters or unicode, so plain character-by-character comparison works.
Approach 1: Brute Force (Try All Rotations)
Intuition
Try every possible rotation of s and check whether any of them equals goal. A string of length n has at most n distinct rotations (including the original), so generating each one and comparing it against goal is enough to cover every case.
To generate the k-th rotation, take the substring from index k to the end and append the substring from index 0 to k. For "abcde" with k=2, that gives "cde" + "ab" = "cdeab".
Algorithm
- If
sandgoalhave different lengths, returnfalse. - For each rotation amount
kfrom0ton - 1: - Build the rotated string:
s[k..n-1] + s[0..k-1]. - If this equals
goal, returntrue. - If no rotation matches, return
false.
Example Walkthrough
Code
- Time Complexity: O(n^2). We try n rotations, and each rotation involves building a new string of length n and comparing it character by character. That's O(n) per rotation, so O(n^2) total.
- Space Complexity: O(n). Each rotation creates a new string of length n.
This rebuilds the entire string for every rotation. The next approach checks every rotation at once, without constructing each one separately.
Approach 2: Concatenate and Search
Intuition
Concatenating s with itself places every possible rotation of s as a contiguous substring inside s + s. For s = "abcde", s + s = "abcdeabcde" contains all five rotations as length-5 windows. The question becomes: is goal a substring of s + s?
The rotation of s by k positions is s[k..n-1] + s[0..k-1]. In s + s, the length-n window starting at index k reads s[k], s[k+1], ..., s[2n-1] wrapped down to s[k-1], which is exactly that rotation. So every rotation of s appears in s + s at some start index between 0 and n-1, and conversely any length-n window of s + s starting in that range is a rotation. Searching for goal inside s + s therefore tests all rotations at once.
The length check before the search is required. Without it, "a" would be found inside "aa" even though "a" is not a rotation of "aa".
Algorithm
- If
sandgoalhave different lengths, returnfalse. - Concatenate
swith itself to getdoubled. - Check if
goalis a substring ofdoubled. - If yes, return
true. Otherwise, returnfalse.
Example Walkthrough
Code
- Time Complexity: Building
s + sis O(n). The cost of the substring search depends on the implementation. The built-incontains/find/includesmethods used here run a naive scan, which is O(n^2) in the worst case (for examples = "aaaa...ab"against many near-matching windows). Using a linear-time string matcher such as KMP brings the search itself to O(n), shown in the next approach. - Space Complexity: O(n). The doubled string holds 2n characters.
This is the shortest solution to write, but the built-in search has an O(n^2) worst case. The next approach makes the same concatenation idea O(n) by replacing the search with KMP.
Approach 3: Concatenation with KMP Search
Intuition
The concatenation idea from Approach 2 is correct: goal is a rotation of s exactly when goal is a substring of s + s (and the lengths match). The only weakness was the search itself, which the built-in methods run as a naive scan. The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern inside a text in O(text + pattern) time, with no quadratic worst case.
Here goal is the pattern and s + s is the text. KMP precomputes a failure function (also called the longest-proper-prefix-suffix table) for goal. When a mismatch occurs partway through a match attempt, the failure function says how far the pattern can shift without rechecking characters already known to match, so the text pointer never moves backward. That is what removes the quadratic behavior.
Algorithm
- If
sandgoalhave different lengths, returnfalse. - Build
text = s + sand treatpattern = goal. - Compute the failure table
lpsforpattern, wherelps[i]is the length of the longest proper prefix ofpattern[0..i]that is also a suffix of it. - Scan
textwith KMP. Keep a pointerjintopattern. For each character oftext: - While
j > 0and the characters mismatch, setj = lps[j - 1]. - If they match, advance
j. - If
jreachespattern.length,patternwas found, so returntrue. - If the scan ends without
jreachingpattern.length, returnfalse.
Example Walkthrough
Code
- Time Complexity: O(n). Building
s + sis O(n). Building the failure table is O(n) in the length ofgoal. The KMP scan processes the 2n-character text in O(n): the text pointerionly moves forward, and the total number of backwardj = lps[j-1]steps across the whole scan is bounded by the number of forward advances, so the scan is linear overall. - Space Complexity: O(n). The doubled string holds 2n characters and the failure table holds n integers.