Problem Statement in English

You’re given two strings s and goal. You have to determine if s can become goal after some number of rotations on s.

Return true if it can, and false otherwise.

Approach

Since we are allowed to rotate the string any number of times, we can think of the string as a circular string.

If goal is a rotation of s, then goal must be a substring of s+s. This is because when we concatenate s with itself, we get all possible rotations of s as substrings.

And we’re done!

Solution in Python


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

Complexity

  • Time: $O(n)$
    Since we check if goal is a substring of s+s which takes $O(n)$ time.

  • Space: $O(n)$
    Since we create a new string s+s which takes $O(n)$ space.

Mistakes I Made

I had to look this up. It didn’t occur to me that if goal is a rotation of s, then goal must be a substring of s+s. This is a neat trick that I will remember for future problems.

And we are done.