Rotate String

Difficulty: Easy | Acceptance: 66.60% | Paid: No Topics: String, String Matching

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.

For example, if s = “abcde”, then it will be “bcdea” after one shift.

• Examples
• Constraints
• Brute Force Rotation
• Concatenation Trick
• KMP Algorithm

Examples

Example 1

Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: We can shift s 2 times to get goal.
- "abcde" -> "bcdea" -> "cdeab"

Example 2

Input: s = "abcde", goal = "abced"
Output: false

Constraints

1 <= s.length, goal.length <= 100
s and goal consist of lowercase English letters.

Brute Force Rotation

Intuition Try every possible rotation of s and check if it matches goal.

Steps

• If lengths differ, return false
• For each rotation count from 0 to n-1:
  • Create rotated string by moving first i characters to end
  • Check if rotated string equals goal
  • If match found, return true
• Return false if no match found

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        n = len(s)
        for i in range(n):
            rotated = s[i:] + s[:i]
            if rotated == goal:
                return True
        return False

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Simple but not optimal for large strings

Concatenation Trick

Intuition If goal is a rotation of s, then goal must be a substring of s + s.

Steps

• If lengths differ, return false
• Concatenate s with itself
• Check if goal is a substring of the concatenated string
• Return result

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

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Elegant solution using string concatenation

KMP Algorithm

Intuition Use Knuth-Morris-Pratt algorithm for efficient substring matching to find goal in s + s.

Steps

• If lengths differ, return false
• Build LPS (Longest Prefix Suffix) array for goal
• Search for goal in s + s using KMP
• Return true if found

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        if not s and not goal:
            return True
        
        def buildLPS(pattern):
            lps = [0] * len(pattern)
            length = 0
            i = 1
            while i < len(pattern):
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            return lps
        
        def kmpSearch(text, pattern):
            lps = buildLPS(pattern)
            i = j = 0
            while i < len(text):
                if text[i] == pattern[j]:
                    i += 1
                    j += 1
                    if j == len(pattern):
                        return True
                else:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return False
        
        return kmpSearch(s + s, goal)

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Most efficient for large strings with many pattern matches