Domain 1EasyCORE

Rotate String

We are given two strings, `A` and `B`. A shift operation on string `A` involves moving its leftmost character to the rightmost position. The task is to determine if string `A` can be transformed into string `B` through any number of such shifts.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 1

796. Rotate String

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 49.1%


Problem Breakdown

We are given two strings, A and B. A shift operation on string A involves moving its leftmost character to the rightmost position. The task is to determine if string A can be transformed into string B through any number of such shifts.

Inputs:

  • Two strings, A and B.

Outputs:

  • A boolean value indicating whether A can become B after some number of shifts.

Implicit Constraints or Tricky Edge Cases:

  • If A and B are empty strings, they are trivially equal.
  • If the lengths of A and B differ, A cannot be transformed into B.
  • Consider cases where A contains duplicate characters.

Intuition

The brute-force approach would involve generating all possible rotations of string A and checking if any of them match string B. However, this approach is inefficient with a time complexity of O(n^2), where n is the length of the string, due to repeated concatenation operations.

A more efficient insight is that if B can be obtained by rotating A, then B must be a substring of some concatenation of A with itself. This reduces the problem to checking if B is a substring of A + A.

Approach

  1. Check Lengths: If the lengths of A and B are different, return False immediately.
  2. Concatenate A with Itself: Create a new string by concatenating A with itself (A + A). This allows us to capture all possible rotations of A.
  3. Substring Check: Use the substring method to check if B is a substring of the concatenated string.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. The concatenation and substring operations are linear.
  • Space Complexity: O(n), due to the creation of the concatenated string.

Solution

def rotateString(A: str, B: str) -> bool:
    # If lengths differ, A cannot be rotated to become B
    if len(A) != len(B):
        return False
    
    # Concatenate A with itself and check if B is a substring
    return B in (A + A)

Edge Cases Handled

  • Empty Strings: Both A and B being empty strings returns True.
  • Different Lengths: If A and B have different lengths, the function returns False immediately.
  • Identical Strings: If A and B are identical, the function returns True as no rotation is needed.