Problem Description

The Rotate String problem asks you to determine whether one string (goal) can be obtained by rotating another string (s). A rotation means moving the leftmost character of the string to the rightmost position, and you can perform this operation any number of times (including zero).

Key constraints:

• BOTH s and goal are non-empty strings of equal length.
• You can rotate s any number of times (possibly zero).
• You must check if after some number of rotations, s becomes exactly equal to goal.

Thought Process

To solve this, let's first think about what it means to "rotate" a string. Every rotation moves the first character to the end, so after each rotation, the string changes slightly. If we try all possible rotations, we might eventually match goal.

The brute-force idea is: for each possible rotation (from 0 up to len(s) - 1), rotate s and check if it matches goal. But this involves creating a lot of intermediate strings, which is inefficient.

Is there a smarter way? Yes! Notice that if we double s (i.e., concatenate s with itself), all possible rotations of s are contained as substrings within this new string. So, we can simply check if goal is a substring of s + s.

Solution Approach

Here’s how we can efficiently solve the problem:

1. Check Lengths: If s and goal are not the same length, it's impossible for one to be a rotation of the other. Return False immediately.
2. Concatenate s with itself: This new string (s + s) contains all possible rotations of s as substrings.
3. Check for Substring: If goal appears anywhere in s + s, then goal is a rotation of s.

This approach avoids generating all rotations one by one and leverages efficient substring search.

Example Walkthrough

Let's use the example s = "abcde" and goal = "cdeab":

• First, check lengths: both are 5, so continue.
• Concatenate s with itself: "abcdeabcde"
• Now, check if "cdeab" is a substring of "abcdeabcde":
• Yes, starting at index 2, "cdeab" appears in "abcdeabcde".
• Therefore, return True because goal is a rotation of s.

If goal was "abced", it would not appear in "abcdeabcde", so we would return False.

Time and Space Complexity

Brute-force approach: For each possible rotation (up to n), create a new string and compare. Each comparison is O(n), so total is O(n²).

Optimized approach: Concatenating s is O(n), and checking if goal is a substring is O(n) (on average, due to efficient implementations like KMP or Boyer-Moore under the hood). So the total time is O(n).

Space complexity: O(n) for the concatenated string.

Summary

The key insight is realizing that all rotations of s are present as substrings in s + s. By checking if goal is a substring, we efficiently solve the problem in linear time and space. This approach avoids unnecessary repeated work and leverages string operations for a concise and elegant solution.

Code Implementation

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

class Solution {
public:
    bool rotateString(string s, string goal) {
        if (s.length() != goal.length()) return false;
        string ss = s + s;
        return ss.find(goal) != string::npos;
    }
};
      

class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        String ss = s + s;
        return ss.contains(goal);
    }
}
      

var rotateString = function(s, goal) {
    if (s.length !== goal.length) return false;
    return (s + s).includes(goal);
};