String Rotation: Check if One String is Rotation of Another in Python

In string manipulation problems, one common interview question is: How to check if one string is a rotation of another? This problem demonstrates clean problem-solving with string algorithms and has real-world applications, such as search engines, DNA sequencing, and pattern recognition. In this article, you will learn how to solve this problem step-by-step, with clear Python implementations, visual explanations, and complexity analysis.

Table of Contents

What is String Rotation?

String rotation means taking characters from the beginning of a string and moving them to the end, while keeping the relative order of all characters intact. For example:

S1 = "ABCD"
Possible rotations are:
"BCDA"
"CDAB"
"DABC"

Here, “BCDA” is formed by moving 'A' from the start of “ABCD” to the end.

Problem Statement

Given two strings S1 and S2, determine whether S2 is a rotation of S1.

Examples

Input: S1 = "ABCD", S2 = "CDAB"
Output: True

Input: S1 = "ABCD", S2 = "ACBD"
Output: False

Key Observation

If S2 is indeed a rotation of S1, then S2 must occur as a substring of S1 + S1.

S1 = "ABCD"
S1 + S1 = "ABCDABCD"

Rotations inside:
"BCDA", "CDAB", "DABC", "ABCD"

Algorithm to Check String Rotation

If lengths of S1 and S2 are different, return False.
Concatenate S1 with itself → S1 + S1.
Check if S2 is a substring of the concatenated string.
If yes, then S2 is a rotation of S1. Otherwise, it is not.

Python Implementation


def is_rotation(s1: str, s2: str) -> bool:
    # Step 1: If lengths differ, can't be rotations
    if len(s1) != len(s2):
        return False
    
    # Step 2: Concatenate s1 with itself
    s1s1 = s1 + s1
    
    # Step 3: Check if s2 is a substring
    return s2 in s1s1

# Example test cases
print(is_rotation("ABCD", "CDAB"))  # True
print(is_rotation("ABCD", "ACBD"))  # False

Output

True
False

Complexity Analysis

Time Complexity: O(N), where N = length of string. The check for substring is O(N) in Python’s efficient implementation.
Space Complexity: O(N), due to storing S1 + S1.

Interactive Visualization

Try rotating "HELLO" step-by-step:

HELLO → ELLOH → LLOHE → LOHEL → OHELL → HELLO

Real-World Applications

DNA Sequencing: DNA strands can be cyclic, meaning one sequence may be a rotation of another.
Security Systems: String shifts are sometimes used in encoding/decoding.
Search Engines: Efficient substring checks play a role in search algorithms.

Conclusion

The string rotation problem is a classic example of solving with elegant logic instead of brute force. By simply checking whether one string is a substring of the other doubled string, we achieve an O(N) solution that is both simple and powerful. Whether you encounter this in interviews or in real applications, remembering this trick will save you from unnecessary complexity.

Now try coding your own version of this problem for different string pairs and test whether they are rotations!