Problem 35.3 · Advanced String AlgorithmsEasy

Rotate String

PatternString Matching (KMP, Z, Rolling Hash)

What it teaches: Every rotation of s is a substring of s + s.

Practise it on judges as “Rotate String”.

In plain words

Rotating a word means taking letters off the front and sticking them on the back, like a train moving carriages from front to back. Every possible rotation of s is sitting inside s written twice in a row, so just check if goal appears in s + s (and has the same length).

Return true if some rotation of s equals goal. Example: s = "abcde", goal = "cdeab" → true.

The problem

Return true if s can become goal after some number of left rotations (moving the first character to the end).

Example 1

Input: s = "abcde", goal = "cdeab"
Output: true

Constraints

1 ≤ lengths ≤ 100

Pattern clues in the wording

→ Rotations

These clues point to String Matching (KMP, Z, Rolling Hash): Find a pattern inside a text in linear time by reusing what earlier comparisons already proved, or by comparing hashes instead of characters.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public boolean rotateString(String s, String goal) {
        return false;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	s = "abcde" goal = "cdeab"	true
2	s = "abcde" goal = "abced"	false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Doubled string search · O(n)

Doubled string search

Time O(n) Space O(n)

Lengths equal and (s + s).contains(goal). Use KMP for a guaranteed O(n).

▶ Dry run: Every rotation lives in s + ss = "abcde", goal = "cdeab"

goal(vars)

cdeabsame length: 5 = 5

Step 1/3Both strings have 5 letters, so a rotation is possible.

Approach 1

class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

Verdict: No rotation simulation needed.

Before you submit

Edge cases and common mistakes

Test these inputs

Different lengths
s equals goal

Mistakes people make

Forgetting the length check ("ab" is inside "abab" for goal "a").

Interview

Follow-up questions

How do you find the lexicographically smallest rotation?

Command Palette

The problem

Approaches

Doubled string search

Edge cases and common mistakes

Follow-up questions