LeetCode 796 - Rotate String

LeetCode Problem 796

Difficulty: 🟢 Easy
Topics: String, String Matching

Solution

Problem Understanding

The problem asks us to determine whether one string can be transformed into another string using repeated left rotations.

A single shift operation removes the first character of the string and appends it to the end. For example:

• "abcde" becomes "bcdea" after one shift
• "bcdea" becomes "cdeab" after another shift

We are given two strings, s and goal, and we must return true if some number of rotations on s can produce goal. Otherwise, we return false.

The important detail is that rotations preserve the relative order of characters. A rotation only changes the starting point of the string. This means the resulting string must still contain the exact same sequence of characters arranged cyclically.

The constraints are very small:

• 1 <= s.length, goal.length <= 100

Since the strings are short, even less efficient approaches would still pass comfortably. However, the goal is to understand the most elegant and optimal solution.

Several edge cases are important:

• The strings may have different lengths. In that case, rotation is impossible.
• The strings may already be equal. Zero rotations are allowed, so the answer should be true.
• Repeated characters can make naive matching tricky. For example, "aaab" and "abaa" are valid rotations even though characters repeat.
• Very small strings, especially length 1, must still work correctly.

Approaches

Brute Force Approach

The brute force solution simulates every possible rotation of s.

A string of length n has exactly n distinct left rotations. We can repeatedly rotate the string one step at a time and compare the result with goal.

For example:

• Start with "abcde"
• Rotate once → "bcdea"
• Rotate again → "cdeab"

If at any point the rotated string equals goal, we return true.

This approach is correct because it explicitly checks every possible valid rotation. If none match, then no rotation can produce goal.

However, repeatedly constructing rotated strings is inefficient. Each rotation costs O(n) time because strings are immutable, and we perform up to n rotations. This leads to O(n²) time complexity.

Optimal Approach

The key insight is that every possible rotation of a string appears as a substring of the string concatenated with itself.

Consider:

s = "abcde"
s + s = "abcdeabcde"

Now look at all length-5 substrings:

• "abcde"
• "bcdea"
• "cdeab"
• "deabc"
• "eabcd"

These are exactly all possible rotations of s.

Therefore:

• If goal is a rotation of s, then goal must appear inside s + s
• The lengths must also match, because rotations never change string length

This gives a very concise and efficient solution:

1. Check if lengths are equal
2. Check whether goal is a substring of s + s

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulates every rotation explicitly
Optimal	O(n)	O(n)	Uses substring search in doubled string

Algorithm Walkthrough

Optimal Algorithm

1. First, compare the lengths of s and goal.

Rotations never change the length of a string. If the lengths differ, it is impossible for goal to be a rotation of s. 2. Create a new string by concatenating s with itself.

For example:

s = "abcde"
doubled = "abcdeabcde"

This doubled string contains every possible rotation of s as a contiguous substring. 3. Check whether goal appears inside the doubled string.

If it does, then some rotation of s matches goal. 4. Return the result of the substring check.

Why it works

Every rotation of a string corresponds to choosing a different starting point in the cyclic ordering of characters. Concatenating the string with itself exposes all cyclic starting positions as normal substrings.

If goal is found inside s + s, then goal matches one of these cyclic shifts exactly. If it is not found, then no valid rotation can produce it.

Python Solution

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False

        doubled = s + s

        return goal in doubled

The implementation begins by checking whether the two strings have equal lengths. This is necessary because rotations preserve the number of characters.

Next, the code creates doubled, which is simply s + s. This combined string contains every possible rotation of s.

Finally, the expression goal in doubled performs a substring search. If goal appears anywhere inside the doubled string, then it must correspond to a valid rotation.

The solution is concise because Python provides efficient built in substring checking.

Go Solution

package main

import "strings"

func rotateString(s string, goal string) bool {
    if len(s) != len(goal) {
        return false
    }

    doubled := s + s

    return strings.Contains(doubled, goal)
}

The Go solution follows exactly the same logic as the Python version.

The primary difference is that Go uses the strings.Contains function for substring searching. Go strings are immutable, just like Python strings, so concatenation creates a new string.

There are no special concerns about integer overflow or nil handling here because the input sizes are extremely small and strings are always valid according to the problem constraints.

Worked Examples

Example 1

Input:
s = "abcde"
goal = "cdeab"

Step 1: Compare lengths

Variable	Value
len(s)	5
len(goal)	5

The lengths match, so rotation is still possible.

Step 2: Concatenate the string with itself

Variable	Value
doubled	"abcdeabcde"

Step 3: Search for goal

We check whether "cdeab" exists inside "abcdeabcde".

Substring Position	Substring
0	"abcde"
1	"bcdea"
2	"cdeab"

A match is found.

Result

true

Example 2

Input:
s = "abcde"
goal = "abced"

Step 1: Compare lengths

Variable	Value
len(s)	5
len(goal)	5

The lengths match.

Step 2: Concatenate

Variable	Value
doubled	"abcdeabcde"

Step 3: Search for goal

We check whether "abced" exists inside "abcdeabcde".

No substring matches "abced".

Result

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Concatenation and substring search both take linear time
Space	O(n)	The doubled string requires additional memory

The algorithm is linear because we only create one additional string of size 2n and perform one substring search. Modern substring search implementations are highly optimized and run efficiently for this input size.

Test Cases

solution = Solution()

assert solution.rotateString("abcde", "cdeab") == True   # standard valid rotation
assert solution.rotateString("abcde", "abced") == False  # not a valid rotation

assert solution.rotateString("a", "a") == True           # single character, identical
assert solution.rotateString("a", "b") == False          # single character, different

assert solution.rotateString("aa", "aa") == True         # repeated characters
assert solution.rotateString("aaab", "abaa") == True     # repeated characters with rotation

assert solution.rotateString("waterbottle", "erbottlewat") == True  # classic rotation case
assert solution.rotateString("rotation", "tationro") == True        # valid multi-step rotation

assert solution.rotateString("abc", "cab") == True       # rotation by two positions
assert solution.rotateString("abc", "bac") == False      # same letters, wrong ordering

assert solution.rotateString("abc", "abcd") == False     # different lengths
assert solution.rotateString("aaaaa", "aaaaa") == True   # all characters identical

Test Case Summary

Test	Why
"abcde" → "cdeab"	Standard successful rotation
"abcde" → "abced"	Invalid rearrangement
"a" → "a"	Smallest valid input
"a" → "b"	Smallest invalid input
"aa" → "aa"	Repeated identical characters
"aaab" → "abaa"	Rotation with duplicates
"waterbottle" → "erbottlewat"	Larger realistic rotation
"rotation" → "tationro"	Multiple shifts required
"abc" → "cab"	Rotation near end of cycle
"abc" → "bac"	Same letters but not rotationally equivalent
"abc" → "abcd"	Length mismatch
"aaaaa" → "aaaaa"	Uniform character string

Edge Cases

Different Length Strings

If s and goal have different lengths, rotation is impossible because rotations never add or remove characters.

For example:

s = "abc"
goal = "abcd"

A naive implementation that only checks substring relationships might accidentally produce incorrect results. The explicit length check prevents this immediately.

Strings That Are Already Equal

The problem allows "some number of shifts", including zero shifts.

For example:

s = "abc"
goal = "abc"

This should return true because no rotation is needed. The doubled string approach naturally handles this case because "abc" is obviously contained in "abcabc".

Repeated Characters

Repeated characters can cause confusion in naive matching logic.

For example:

s = "aaab"
goal = "abaa"

Even though the string contains duplicate 'a' characters, the doubled string still correctly represents every valid cyclic rotation. Substring search handles repeated patterns safely and accurately.