Write a Code to check whether one string is a rotation of another

The problem, simply

You get two strings, s1 and s2. A rotation takes some letters from the front of a string and moves them to the back, keeping their order. For example, abcde rotated by 2 is cdeab.

Say true if s2 is some rotation of s1, and false otherwise. Both strings have length n when the answer can be true.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every turn of the necklace.

1. If the lengths differ, return false.
2. For each shift k from 0 to n - 1, compare s1 read from position k (wrapping around) with s2, letter by letter.
3. If one shift matches every letter, return true.

class Solution {
    public boolean isRotation(String s1, String s2) {
        int n = s1.length();
        if (n != s2.length()) return false;
        if (n == 0) return true;
        for (int k = 0; k < n; k++) {                       // turn the necklace by k
            int i = 0;
            while (i < n && s1.charAt((k + i) % n) == s2.charAt(i)) i++;
            if (i == n) return true;                        // every bead matched
        }
        return false;
    }
}

How long it takes: n shifts, and each may compare up to n letters, so O(n^2). Extra room: none, O(1), since we read around the circle with % n instead of building new strings.

Way 2: the clever way

Lay the necklace out twice. Every rotation of s1 is a block of n letters inside s1 + s1. So s2 is a rotation exactly when the lengths match and s2 appears inside s1 + s1.

1. If the lengths differ, return false.
2. Build doubled = s1 + s1.
3. Search for s2 inside doubled with KMP, a search that never moves backwards in the long string.

KMP keeps a cheat sheet for s2: after a wrong letter, how much of what we matched can still count. For cdeab all letters differ, so the sheet is all zeros and a mismatch sends the word finger back to the start.

class Solution {
    public boolean isRotation(String s1, String s2) {
        if (s1.length() != s2.length()) return false;   // must be the same necklace size
        if (s1.isEmpty()) return true;
        String doubled = s1 + s1;                       // every turn is a window in here
        return kmpFind(doubled, s2) >= 0;
    }

    // cheat sheet: for each prefix of p, the longest part that is also a suffix
    private int[] fallback(String p) {
        int[] t = new int[p.length()];
        for (int i = 1, len = 0; i < p.length(); ) {
            if (p.charAt(i) == p.charAt(len)) t[i++] = ++len;
            else if (len > 0) len = t[len - 1];
            else t[i++] = 0;
        }
        return t;
    }

    // first place where p starts in text, or -1; the text finger never goes back
    private int kmpFind(String text, String p) {
        int[] t = fallback(p);
        for (int i = 0, j = 0; i < text.length(); ) {
            if (text.charAt(i) == p.charAt(j)) {
                i++;
                j++;
                if (j == p.length()) return i - j;
            } else if (j > 0) {
                j = t[j - 1];        // keep the part that still counts
            } else {
                i++;
            }
        }
        return -1;
    }
}

How long it takes: building the doubled string is O(n), the cheat sheet is O(n), and the search reads 2n letters without going back, so O(n) in total. Extra room: the doubled string and the cheat sheet, O(n).

In many interviews the one line s1.length() == s2.length() && (s1 + s1).contains(s2) is accepted. Say out loud that Java's contains can take O(n^2) on bad inputs like aaaa...ab, and KMP fixes that.

Watch out for

• Comparing only letter counts. abcde and abced have the same letters but are not rotations.
• Building a new string for every shift in Way 1 with substring. It works, but it costs O(n) extra room per shift. Reading with % n avoids it.
• Empty strings. Decide up front: two empty strings are rotations of each other.

What interviewers ask next

• By how much was it turned? The KMP match position is the shift. Here cdeab starts at 2, so s1 was turned left by 2.
• Can you check without the extra O(n) room? Yes, Way 1 uses O(1) room but O(n^2) time. Getting both O(n) time and O(1) room needs a cleverer string algorithm, such as comparing the smallest rotation of each (Booth's or the two pointer minimum rotation).
• Rotate an array by k in place. Reverse the first k items, reverse the rest, then reverse the whole thing.
• Group strings that are rotations of each other. Map each string to its smallest rotation and use that as the key.

Remember this

Grown-up words: the necklace is a cyclic string, laying it out twice is string doubling (concatenation), the search that never goes back is the Knuth Morris Pratt algorithm, and its cheat sheet is the failure function or LPS array.