Check if String is Rotation of Another

Determine if one string is a rotation of another string by checking if it can be formed by rotating the characters.

Language Selection

Choose your preferred programming language

Showing: Python

Check if String is Rotation of Another

Problem Statement

Given two strings s1 and s2, determine if s2 is a rotation of s1. A rotation means that we can obtain s2 by rotating the characters of s1 by some number of positions.

Examples

Example 1:

Input: s1 = "waterbottle", s2 = "erbottlewat"
Output: true
Explanation: "erbottlewat" is a rotation of "waterbottle"

Example 2:

Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: "cdab" is a rotation of "abcd"

Example 3:

Input: s1 = "hello", s2 = "world"
Output: false
Explanation: "world" is not a rotation of "hello"

Constraints

1 <= s1.length, s2.length <= 100
s1 and s2 consist of lowercase English letters only

Approach 1: Concatenation Method

Algorithm

The key insight is that if s2 is a rotation of s1, then s2 must be a substring of s1 + s1. This is because when we concatenate s1 with itself, all possible rotations of s1 become substrings of the concatenated string.

Steps:

Check if the lengths of both strings are equal
Concatenate s1 with itself
Check if s2 is a substring of the concatenated string

Implementation

Python:

def is_rotation(s1, s2):
    """
    Check if s2 is a rotation of s1 using concatenation method
    Time: O(n)
    Space: O(n)
    """
    if len(s1) != len(s2):
        return False
    
    concatenated = s1 + s1
    return s2 in concatenated

Java:

class Solution {
    /**
     * Check if s2 is a rotation of s1 using concatenation method
     * Time: O(n)
     * Space: O(n)
     */
    public boolean isRotation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        
        String concatenated = s1 + s1;
        return concatenated.contains(s2);
    }
}

Go:

// isRotation - Check if s2 is a rotation of s1 using concatenation method
// Time: O(n)
// Space: O(n)
func isRotation(s1, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    
    concatenated := s1 + s1
    return strings.Contains(concatenated, s2)
}

JavaScript:

/**
 * Check if s2 is a rotation of s1 using concatenation method
 * Time: O(n)
 * Space: O(n)
 */
function isRotation(s1, s2) {
    if (s1.length !== s2.length) {
        return false;
    }
    
    const concatenated = s1 + s1;
    return concatenated.includes(s2);
}

C#:

public class Solution {
    /// <summary>
    /// Check if s2 is a rotation of s1 using concatenation method
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public bool IsRotation(string s1, string s2) {
        if (s1.Length != s2.Length) {
            return false;
        }
        
        string concatenated = s1 + s1;
        return concatenated.Contains(s2);
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the strings
Space Complexity: O(n) for the concatenated string

Approach 2: Character-by-Character Comparison

Algorithm

This approach simulates the rotation by comparing characters at different starting positions.

Steps:

Check if lengths are equal
For each possible rotation point in s1
Compare characters of s2 with rotated characters of s1

Implementation

Python:

def is_rotation_brute_force(s1, s2):
    """
    Check if s2 is a rotation of s1 using brute force comparison
    Time: O(n²)
    Space: O(1)
    """
    if len(s1) != len(s2):
        return False
    
    n = len(s1)
    for i in range(n):
        if all(s2[j] == s1[(i + j) % n] for j in range(n)):
            return True
    return False

Java:

class Solution {
    /**
     * Check if s2 is a rotation of s1 using brute force comparison
     * Time: O(n²)
     * Space: O(1)
     */
    public boolean isRotationBruteForce(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            boolean isRotation = true;
            for (int j = 0; j < n; j++) {
                if (s2.charAt(j) != s1.charAt((i + j) % n)) {
                    isRotation = false;
                    break;
                }
            }
            if (isRotation) {
                return true;
            }
        }
        return false;
    }
}

Go:

// isRotationBruteForce - Check if s2 is a rotation of s1 using brute force comparison
// Time: O(n²)
// Space: O(1)
func isRotationBruteForce(s1, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    
    n := len(s1)
    for i := 0; i < n; i++ {
        isRotation := true
        for j := 0; j < n; j++ {
            if s2[j] != s1[(i+j)%n] {
                isRotation = false
                break
            }
        }
        if isRotation {
            return true
        }
    }
    return false
}

JavaScript:

/**
 * Check if s2 is a rotation of s1 using brute force comparison
 * Time: O(n²)
 * Space: O(1)
 */
function isRotationBruteForce(s1, s2) {
    if (s1.length !== s2.length) {
        return false;
    }
    
    const n = s1.length;
    for (let i = 0; i < n; i++) {
        let isRotation = true;
        for (let j = 0; j < n; j++) {
            if (s2[j] !== s1[(i + j) % n]) {
                isRotation = false;
                break;
            }
        }
        if (isRotation) {
            return true;
        }
    }
    return false;
}

C#:

public class Solution {
    /// <summary>
    /// Check if s2 is a rotation of s1 using brute force comparison
    /// Time: O(n²)
    /// Space: O(1)
    /// </summary>
    public bool IsRotationBruteForce(string s1, string s2) {
        if (s1.Length != s2.Length) {
            return false;
        }
        
        int n = s1.Length;
        for (int i = 0; i < n; i++) {
            bool isRotation = true;
            for (int j = 0; j < n; j++) {
                if (s2[j] != s1[(i + j) % n]) {
                    isRotation = false;
                    break;
                }
            }
            if (isRotation) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n²) where n is the length of the strings
Space Complexity: O(1)

Key Insights

Concatenation Trick: The most elegant solution uses the fact that all rotations of a string appear as substrings when the string is concatenated with itself.
Length Check: Always check if both strings have the same length first, as rotations must preserve length.
Substring Search: Most languages provide efficient substring search algorithms (like KMP or Boyer-Moore) that make the concatenation approach very efficient.
Modular Arithmetic: The brute force approach uses modular arithmetic (i + j) % n to simulate circular rotation.

Edge Cases

Empty strings: Both strings are empty (considered a rotation)
Single character: Both strings have one character
Identical strings: Same string is always a rotation of itself
Different lengths: Strings of different lengths cannot be rotations
All same characters: Strings like “aaaa” and “aaaa”

Test Cases

# Test cases
assert is_rotation("waterbottle", "erbottlewat") == True
assert is_rotation("abcd", "cdab") == True
assert is_rotation("hello", "world") == False
assert is_rotation("", "") == True
assert is_rotation("a", "a") == True
assert is_rotation("ab", "ba") == True
assert is_rotation("abc", "bca") == True
assert is_rotation("abc", "acb") == False

Follow-up Questions

Count Rotations: How many different rotations does a string have?
Find Rotation Point: Given a rotated sorted array, find the rotation point
Minimum Rotations: Find the minimum number of rotations to make two strings equal
Circular Array: Check if one array is a rotation of another

Common Mistakes

Forgetting length check: Not checking if strings have equal lengths
Off-by-one errors: Incorrect indexing in modular arithmetic
Case sensitivity: Not considering case differences
Empty string handling: Not properly handling edge cases

Interview Tips

Start with examples: Walk through examples to understand the problem
Think about properties: What properties must rotations have?
Optimize step by step: Start with brute force, then optimize
Consider edge cases: Always think about boundary conditions
Explain the insight: The concatenation trick is the key insight to highlight