We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rotate String

Difficulty: Easy

Problem Description

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s. A shift on s consists of moving the leftmost character of s to the rightmost position.

Key Insights

  • A string s can be rotated to form another string goal if both strings have the same length and contain the same characters.
  • If we concatenate s with itself (i.e., s + s), all possible rotations of s will appear as substrings within this new string.
  • Thus, to check if goal is a valid rotation of s, we can simply verify if goal is a substring of s + s.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. We perform a substring search within a string of length 2n. Space Complexity: O(1), since we are not using any additional data structures that scale with input size.

Solution

The solution involves checking if the length of both strings is the same and if goal appears as a substring in the concatenated string s + s. This approach uses simple string manipulation and substring checking.

Code Solutions

def rotateString(s: str, goal: str) -> bool:
    # Check if lengths are the same
    if len(s) != len(goal):
        return False
    # Check if goal is a substring of s + s
    return goal in (s + s)
← Back to All Questions