☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Rotate String

Easy TUF ID 398 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given two strings s and goal. A shift (or rotation) of s moves its first character to the end: "abcde" becomes "bcdea". Return true if goal can be obtained from s after some number of shifts (zero shifts included), and false otherwise.

Constraints: 0 ≤ |s|, |goal| ≤ 100 in the LeetCode version; the approaches below scale to 10^5 characters. Lowercase English letters.

Example 1

s = "abcde", goal = "cdeab"
answer = true          // two shifts: abcde -> bcdea -> cdeab

Example 2

s = "abcde", goal = "abced"
answer = false         // same letters, but no rotation of abcde ends in "ed"

Example 3

s = "aaab", goal = "abaa"
answer = true          // abaa is the rotation that starts at index 2

Approach 1: Brute force, generate every rotation

Intuition. There are only n distinct rotations of a string of length n (shifting n times brings it back to the start), so we can simply produce each of them and compare with goal. The rotation after k shifts is the suffix starting at k followed by the prefix of length k: s.substring(k) + s.substring(0, k).

Algorithm.

  1. If the lengths differ, return false. If s is empty, return true (the empty string is a rotation of itself).
  2. For k from 0 to n - 1: build rotated = s[k..n) + s[0..k); if it equals goal, return true.
  3. Return false.
static boolean bruteForce(String s, String goal) {
    if (s.length() != goal.length()) return false;
    if (s.isEmpty()) return true;
    int n = s.length();
    for (int k = 0; k < n; k++) {                          // k = number of left shifts
        String rotated = s.substring(k) + s.substring(0, k);
        if (rotated.equals(goal)) return true;
    }
    return false;
}

Complexity. Time O(n^2): n rotations, each costing O(n) to build and compare. Space O(n) for the current rotation.

An in-place variant compares s[(k + i) mod n] with goal[i] for each i without building the rotated string; that removes the allocation but is still O(n^2) in the worst case.

Approach 2: Better, every rotation is a substring of s + s

Intuition. Write s twice in a row: "abcdeabcde". Every rotation of s appears in this doubled string as a contiguous window of length n: the rotation that starts at index k is exactly (s + s)[k..k+n). The converse also holds: any window of length n in s + s that starts at k < n is a rotation of s, and the window starting at k = n is s itself again. So goal is a rotation of s if and only if goal has length n and occurs in s + s. The length check is essential: "ab" is a substring of "abcabc" but is not a rotation of "abc".

Algorithm.

  1. If the lengths differ, return false.
  2. Return whether s + s contains goal.
static boolean better(String s, String goal) {
    return s.length() == goal.length() && (s + s).contains(goal);
}

Complexity. Time: String.contains in the JDK is a straightforward search whose worst case is O(n · m), here O(n^2), but on typical inputs it runs close to linear. Space O(n) for the doubled string.

This is the version to write in an interview first: one line, obviously correct once the doubling idea is explained. If the interviewer asks for a guaranteed linear bound, that is the cue for Approach 3.

Intuition. The only non-linear step above is the substring search, and the Knuth-Morris-Pratt algorithm searches for a pattern of length m in a text of length L in O(L + m) time regardless of the input. KMP precomputes, for the pattern goal, the table lps[i] = length of the longest proper prefix of goal[0..i] that is also a suffix of it. During the scan it keeps j, the number of pattern characters matched so far. On a mismatch it does not restart from the beginning of the pattern; it falls back to j = lps[j - 1], the longest border of what was matched, because those characters are already known to line up with the text.

Algorithm.

  1. If the lengths differ, return false. If s is empty, return true.
  2. Let text = s + s and compute lps for goal.
  3. Scan text with j = 0:
    • While j > 0 and text[i] != goal[j], set j = lps[j - 1].
    • If text[i] == goal[j], increment j.
    • If j == |goal|, a full match ends at i: return true.
  4. Return false.
static boolean optimal(String s, String goal) {
    if (s.length() != goal.length()) return false;
    if (s.isEmpty()) return true;
    String text = s + s;
    int[] lps = buildLps(goal);
    int j = 0;                                             // number of characters of goal matched so far
    for (int i = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != goal.charAt(j)) j = lps[j - 1];
        if (text.charAt(i) == goal.charAt(j)) j++;
        if (j == goal.length()) return true;
    }
    return false;
}

static int[] buildLps(String p) {
    int[] lps = new int[p.length()];
    int len = 0;
    for (int i = 1; i < p.length(); i++) {
        while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
        if (p.charAt(i) == p.charAt(len)) len++;
        lps[i] = len;
    }
    return lps;
}

Dry run of the search on s = "abcde", goal = "cdeab", text = "abcdeabcde". The pattern has no repeated characters, so lps = [0, 0, 0, 0, 0].

i text[i] j before action j after
0 a 0 a != c, j stays 0 0
1 b 0 b != c 0
2 c 0 match 1
3 d 1 match 2
4 e 2 match 3
5 a 3 match 4
6 b 4 match, j == 5, return true 5

The fallback shows its value on patterns with repeated characters. Searching for "aab" (lps = [0, 1, 0]) in "aaab": after matching "aa" the scan sees a third a where the pattern wants b. A naive search would restart from scratch one position later; KMP sets j = lps[1] = 1, keeping one matched a, compares the new a with goal[1], matches, and then matches b on the next character. No text character is ever re-read. In the "aaab"/"abaa" test of the Java file the fallbacks are from j = 1 to lps[0] = 0 at i = 1 and i = 2, and the match is found at i = 5.

Complexity. Time O(n): building lps is O(n) and the scan over the 2n-character text is O(n), because j increases at most 2n times and every fallback decreases it, so the total number of fallbacks is bounded by the number of increases. Space O(n) for text and lps.

The j == goal.length() check happens right after the increment and returns at once, so goal.charAt(j) is never evaluated with j == |goal|. A general-purpose KMP that reports all occurrences would set j = lps[j - 1] here and continue instead.

Edge cases and pitfalls