Rotate String - Video Solutions

Problem Overview: You are given two strings s and goal. The task is to determine whether repeatedly rotating s (moving the first character to the end) can produce goal. If any number of rotations results in the target string, return true; otherwise return false.

Approach 1: Brute Force with Rotation Simulation (O(n²) time, O(1) space)

The straightforward way is to simulate every possible rotation of s. For each rotation, move the first character to the end and compare the new string with goal. Since a string of length n has exactly n possible rotations, you repeat this process up to n times. Each comparison takes O(n) time, leading to an overall time complexity of O(n²) while using constant extra space.

This approach clearly demonstrates the rotation behavior and is easy to reason about. However, it becomes inefficient for longer strings because every rotation requires rebuilding or comparing the full string. Still, it’s useful when first understanding the problem or when implementing a direct simulation using basic string operations.

Approach 2: Concatenation Check (O(n) time, O(n) space)

A key observation simplifies the problem: if you concatenate s with itself (s + s), every possible rotation of s appears as a substring of this combined string. For example, if s = "abcde", then s + s = "abcdeabcde", which contains "bcdea", "cdeab", and every other rotation.

The solution becomes simple. First check that s and goal have the same length. If not, a rotation can never match. If lengths match, compute s + s and check whether goal exists as a substring. Modern substring search implementations run in O(n) time on average using optimized string matching techniques. The additional concatenated string requires O(n) space.

This trick avoids explicitly generating each rotation. Instead, it leverages how rotations naturally appear within a doubled string. The result is cleaner code and significantly better performance compared with simulation.

Recommended for interviews: Interviewers usually expect the concatenation insight. The brute force rotation simulation shows you understand the mechanics of the problem, but recognizing that goal must be a substring of s + s demonstrates stronger pattern recognition and familiarity with common string problem tricks.