Strings Rotations of Each Other

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Check if two strings are rotations of each other.

See our study guide for structured GFG and LeetCode practice.

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?