Problem Description

You are given two strings s and goal. Your task is to determine if string s can be transformed into string goal through a series of shift operations.

A shift operation takes the leftmost character of the string and moves it to the rightmost position. For instance:

• Starting with s = "abcde"
• After 1 shift: "bcdea" (moved 'a' to the end)
• After 2 shifts: "cdeab" (moved 'b' to the end)
• After 3 shifts: "deabc" (moved 'c' to the end)
• And so on...

The function should return true if it's possible to obtain goal from s after any number of shifts (including zero shifts), and false otherwise.

The solution leverages a clever observation: if goal can be obtained by rotating s, then goal must appear as a substring within s + s (the concatenation of s with itself). This works because s + s contains all possible rotations of s as substrings. Additionally, the lengths of both strings must be equal for a valid rotation to exist.

For example, if s = "abcde", then s + s = "abcdeabcde", which contains all rotations: "abcde", "bcdea", "cdeab", "deabc", and "eabcd".

Intuition

The key insight comes from visualizing what happens when we continuously shift a string. If we keep shifting s = "abcde", we get:

• Original: "abcde"
• 1 shift: "bcdea"
• 2 shifts: "cdeab"
• 3 shifts: "deabc"
• 4 shifts: "eabcd"
• 5 shifts: "abcde" (back to original)

Notice that after n shifts (where n is the length of the string), we return to the original string. This creates a cycle of all possible rotations.

Now, imagine writing the string twice in a row: "abcdeabcde". If we look at this doubled string, we can find every possible rotation as a substring of length n:

• Starting at index 0: "abcde" (0 shifts)
• Starting at index 1: "bcdea" (1 shift)
• Starting at index 2: "cdeab" (2 shifts)
• Starting at index 3: "deabc" (3 shifts)
• Starting at index 4: "eabcd" (4 shifts)

This pattern reveals that s + s contains all possible rotations of s as contiguous substrings. Therefore, if goal is a valid rotation of s, it must appear somewhere within s + s.

The length check len(s) == len(goal) is necessary because a rotation preserves the string length. Without this check, we might incorrectly match substrings of different lengths.

This elegant approach reduces the rotation problem to a simple substring search, avoiding the need to explicitly generate and check each possible rotation.

Solution Approach

The implementation is remarkably concise, using a string concatenation and substring search approach:

def rotateString(self, s: str, goal: str) -> bool:
    return len(s) == len(goal) and goal in s + s

Let's break down the solution step by step:

1. Length Check: len(s) == len(goal)

   • First, we verify that both strings have the same length
   • This is a necessary condition since rotation doesn't change the string length
   • If lengths differ, we can immediately return false

2. String Concatenation: s + s

   • We create a new string by concatenating s with itself
   • For example, if s = "abcde", then s + s = "abcdeabcde"
   • This doubled string contains all possible rotations as substrings

3. Substring Search: goal in s + s

   • Python's in operator checks if goal exists as a substring in the concatenated string
   • This operation has a time complexity of O(n) in Python's implementation using efficient string matching algorithms

4. Combined Logic: The return statement uses and to ensure both conditions are met:

   • Equal lengths AND goal is found in the doubled string

Example Walkthrough:

• Input: s = "abcde", goal = "cdeab"
• Check: len("abcde") == len("cdeab") → 5 == 5 → True
• Concatenate: "abcde" + "abcde" = "abcdeabcde"
• Search: Is "cdeab" in "abcdeabcde"? → Yes (at index 2)
• Result: True and True → True

Time Complexity: O(n) where n is the length of the string, for the substring search operation.

Space Complexity: O(n) for creating the concatenated string s + s.

Example Walkthrough

Let's walk through a concrete example with s = "abc" and goal = "cab".

Step 1: Check if lengths are equal

• len("abc") = 3
• len("cab") = 3
• Lengths match ✓

Step 2: Create the doubled string

• s + s = "abc" + "abc" = "abcabc"

Step 3: Visualize all rotations in the doubled string

"abcabc"
 ^^^     → "abc" (0 shifts - original)
  ^^^    → "bca" (1 shift - 'a' moved to end)
   ^^^   → "cab" (2 shifts - 'ab' moved to end)

Step 4: Check if goal exists in doubled string

• Is "cab" in "abcabc"?
• Yes! It appears starting at index 2

Step 5: Return result

• Both conditions satisfied: equal length AND substring found
• Return True

Counter-example: If goal = "acb" instead:

• s + s = "abcabc"
• Is "acb" in "abcabc"? No!
• This makes sense because "acb" is not a rotation of "abc" - it would require rearranging characters, not just shifting
• Return False

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) in the worst case, where n is the length of string s.

The algorithm first checks if lengths are equal (O(1)), then concatenates s with itself creating s + s (O(n)), and finally performs substring search using the in operator to check if goal exists in s + s. The substring search operation in Python uses a pattern matching algorithm that has O(n*m) complexity in the worst case, where n is the length of the text being searched and m is the length of the pattern. Since we're searching for goal (length n) in s + s (length 2n), this gives us O(2n * n) = O(n²) worst-case time complexity.

Space Complexity: O(n), where n is the length of string s.

The concatenation s + s creates a new string of length 2n, which requires O(2n) = O(n) additional space. The in operator itself may use some additional space for the pattern matching algorithm, but this is typically O(1) or at most O(n) depending on the implementation, so the overall space complexity remains O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the Length Check

One of the most common mistakes is omitting the length equality check and only relying on the substring search.

Incorrect Implementation:

def rotateString(self, s: str, goal: str) -> bool:
    return goal in s + s  # Missing length check!

Why it fails: Without the length check, the function would incorrectly return True for cases where goal is a substring but not a complete rotation.

• Example: s = "abcde", goal = "cde"
• s + s = "abcdeabcde" contains "cde" as a substring
• But "cde" is NOT a rotation of "abcde" (different lengths)

Solution: Always include the length check:

def rotateString(self, s: str, goal: str) -> bool:
    return len(s) == len(goal) and goal in s + s

2. Edge Case: Empty Strings

While the current solution handles empty strings correctly, developers might overthink and add unnecessary special case handling.

Overcomplicated Implementation:

def rotateString(self, s: str, goal: str) -> bool:
    if not s and not goal:
        return True
    if not s or not goal:
        return False
    return len(s) == len(goal) and goal in s + s

Why it's unnecessary: The original solution already handles empty strings correctly:

• If both are empty: len("") == len("") is True, and "" in "" is True
• If only one is empty: The length check fails, returning False

Solution: Trust the elegance of the original solution - it handles edge cases naturally.

3. Attempting Manual Rotation Instead of Using the Concatenation Trick

Some developers might try to manually perform rotations, leading to more complex and error-prone code.

Inefficient Implementation:

def rotateString(self, s: str, goal: str) -> bool:
    if len(s) != len(goal):
        return False
    for i in range(len(s)):
        if s[i:] + s[:i] == goal:  # Manual rotation
            return True
    return False

Why it's problematic:

• More complex code with higher chance of bugs
• O(n²) time complexity due to string slicing and comparison in a loop
• Less readable and harder to maintain

Solution: Use the concatenation approach for O(n) time complexity and cleaner code:

def rotateString(self, s: str, goal: str) -> bool:
    return len(s) == len(goal) and goal in s + s

4. Misunderstanding the Problem: Confusing Shift with Other Operations

Some might confuse "shift" operations with character swapping or reversing.

Wrong Interpretation Example: Thinking that transforming "abcde" to "edcba" (reverse) is possible through shifts. It's not - shifts only move characters from front to back, maintaining their relative order.

Solution: Remember that a shift operation only moves the leftmost character to the rightmost position. All valid rotations maintain the cyclic order of characters.