Rotate String | Leetcode 796 | Optimal Substring Search Solution

The Rotate String problem asks us to check whether one string goal can be obtained by rotating another string s.

• A rotation means repeatedly moving the leftmost character of a string to the rightmost position.
• We need to return True if after some number of rotations, s can become goal; otherwise return False.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: "abcde" → "bcdea" → "cdeab"

Example 2

Input: s = "abcde", goal = "abced"
Output: false
Explanation: No rotation of "abcde" equals "abced".

Intuition and Approach

To solve Rotate String, let’s analyze:

1. Rotation property:
   • If you rotate a string s, the result is always a substring of s+s.
   • Example: s = "abcde" → s+s = "abcdeabcde".
     • All possible rotations ("abcde", "bcdea", "cdeab", "deabc", "eabcd") are substrings of "abcdeabcde".
2. Algorithm:
   • Check if lengths of s and goal are equal. If not, return False.
   • Create string = s + s.
   • If goal is a substring of string, return True. Otherwise return False.

This trick is both simple and optimal, avoiding the need to simulate rotations.

Code Implementation

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

Code Explanation

1. Length check:
   • If s and goal have different lengths, rotation is impossible.
2. Concatenate string:
   • s + s contains all possible rotations of s.
3. Substring check:
   • If goal is in s+s, then goal is a valid rotation.
   • Otherwise, return False.

Dry Run

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

• Check lengths: both length = 5 → valid.
• Concatenate: "abcde" + "abcde" = "abcdeabcde".
• Check substring: "cdeab" in "abcdeabcde" → True.

Output: True.

Time and Space Complexity

• Time Complexity:
  • Concatenation takes O(N).
  • Substring search takes O(N) (average, depending on implementation).
    Overall: O(N), where N is the length of the string.
• Space Complexity:
  • We create s+s, which takes O(N) extra space.

Conclusion

The Rotate String problem can be solved optimally using the property that all rotations of a string appear as substrings of s+s.

• Avoids explicit rotation simulation.
• Runs in O(N) time and space.
• Clean and elegant one-liner:

return len(s) == len(goal) and goal in (s+s)

This solution is both interview-friendly and competitive programming optimal.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.