796. Rotate String

EasyView on LeetCode

String String Matching

Time: O(n)

Space: O(n)

Problem Overview

String rotation means shifting characters cyclically — e.g.

Intuition

String rotation means shifting characters cyclically — e.g. "abcde" rotated by 2 is "cdeab". Key insight: every rotation of B appears as a contiguous substring inside B+B, so A is a rotation of B iff lengths match and A occurs in B+B.

Algorithm

1If A.Length != B.Length, return false immediately.
2Concatenate B + B into one string.
3Return whether that concatenation contains A as a substring (IndexOf / KMP).

Example Walkthrough

Input: s = "rotation", goal = "tionrota"

1.Lengths both 8 — OK.
2.goal + goal contains "rotation" as substring starting at index 3.

Output: true

Common Pitfalls

•Always check equal lengths first — avoids false positives on different sizes.
•Empty strings: two empty strings are rotations of each other.
•IndexOf is O(n²) worst case; KMP is O(n) if interviewer asks for optimization.

796.cs

// Approach: A rotation of s equals goal iff goal is a substring of the doubled string s+s.
// Time: O(n) Space: O(n)

public class Solution
{
    public bool RotateString(string s, string goal)
    {
        int n = s.Length;
        int m = goal.Length;

        if (n != m)
            return false;

        string temp = s + s;
        return temp.Contains(goal);
    }
}

Was this solution helpful?