DSA 450 Notes

Problem Statement

Given two strings s1 and s2, check if s2 is a rotation of s1. A string rotation means taking some characters from the beginning and moving them to the end.

Example:

Input: s1 = "abcde", s2 = "cdeab"
Output: true
Explanation: Rotating "abcde" by 2 positions gives "cdeab"
Input: s1 = "abcde", s2 = "abced"
Output: false

Approach 1: Brute Force (Check All Rotations)

Intuition

Generate all possible rotations of s1 and check if any of them equals s2.

Algorithm

If lengths are different, return false
Generate all n rotations of s1
Compare each rotation with s2
Return true if any rotation matches

java

public class Solution {
    public boolean isRotation(String s1, String s2) {
        int n = s1.length();
        if (n != s2.length()) return false;
        if (n == 0) return true;
        
        // Try all rotations
        for (int i = 0; i < n; i++) {
            // Generate rotation starting at index i
            String rotated = s1.substring(i) + s1.substring(0, i);
            if (rotated.equals(s2)) return true;
        }
        
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n²) - n rotations, each comparison takes O(n)
Space Complexity: O(n) - For the rotated string

Approach 2: Optimal (Concatenation Trick)

Intuition

If s2 is a rotation of s1, then s2 will always be a substring of s1 + s1.

For example:

s1 = "abcde"
s1 + s1 = "abcdeabcde"
All rotations: "abcde", "bcdea", "cdeab", "deabc", "eabcd" are substrings of "abcdeabcde"

Algorithm

If lengths are different, return false
Concatenate s1 with itself: temp = s1 + s1
Check if s2 is a substring of temp
Return the result

java

public class Solution {
    public boolean isRotation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.isEmpty()) {
            return true;
        }
        
        // Concatenate s1 with itself
        String temp = s1 + s1;
        
        // Check if s2 is a substring of temp
        return temp.contains(s2);
    }
}

Complexity Analysis

Time Complexity: O(n) - String concatenation O(n) + substring search O(n) with optimized algorithms
Space Complexity: O(n) - For the concatenated string

Approach 3: Using KMP for Substring Search

Intuition

Instead of relying on built-in substring search, use KMP algorithm for guaranteed O(n) time complexity.

java

public class Solution {
    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    private boolean kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPS(pattern);
        
        int i = 0, j = 0;
        while (i < n) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }
            
            if (j == m) {
                return true;
            } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return false;
    }
    
    public boolean isRotation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.isEmpty()) {
            return true;
        }
        
        String temp = s1 + s1;
        return kmpSearch(temp, s2);
    }
}

Complexity Analysis

Time Complexity: O(n) - KMP guarantees linear time
Space Complexity: O(n) - For concatenated string and LPS array

Key Takeaways

Concatenation trick is a clever way to check all rotations at once
If s2 is a rotation of s1, then s2 is always a substring of s1 + s1
Built-in substring methods like find(), contains(), or in are usually optimized
For guaranteed O(n) complexity, use KMP or similar algorithms
Always check length equality first as an early exit condition
This problem demonstrates how a seemingly O(n²) problem can be reduced to O(n)

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

Problem Statement

Approach 1: Brute Force (Check All Rotations)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Concatenation Trick)

Intuition

Algorithm

Complexity Analysis

Approach 3: Using KMP for Substring Search

Intuition

Complexity Analysis

Key Takeaways