Strings Rotations of Each Other

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Check if two strings are rotations of each other. If s2 is in s1+s1, they are rotations.

Algorithm

1If lengths differ: false. Else: check if s2 is substring of (s1+s1).

Common Pitfalls

•Same as LC 796. KMP or indexOf on concatenated string. O(n) with KMP, O(n^2) with naive substring.

Strings Rotations of Each Other.java

Java

// Approach: Concatenate s1 with itself. Check if s2 is a substring using KMP or contains().
// Time: O(n) Space: O(n)
class Solution {
    // Function to check if two strings are rotations of each other or not.
    public static boolean areRotations(String s1, String s2) {
        StringBuilder obj = new StringBuilder(s2);
        int m = s2.length();
        obj.append('$');
        obj.append(s1);
        obj.append(s1);
        s1 = new String(obj);
        int n = s1.length();
        int lps[] = new int[n];
        int len = 0;
        int i = 1;
        while (i < n) {
            if (s1.charAt(i) == s1.charAt(len)) {
                len++;
                if (len == m)
                    return true;
                lps[i] = len;
                i++;
            } else {
                if (len > 0)
                    len = lps[len - 1];
                else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return false;
    }
}

Was this solution helpful?