796. Rotate String - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

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 consists of moving the leftmost character of s to the rightmost position.

Example Inputs and Outputs:

  1. Input: s = "abcde", goal = "cdeab"
    Output: true
    Explanation: "abcde" can be rotated to "cdeab" after 3 shifts.

  2. Input: s = "abcde", goal = "abced"
    Output: false
    Explanation: No possible rotation of "abcde" results in "abced".

  3. Input: s = "", goal = ""
    Output: true
    Explanation: Both are empty strings, which means one is a rotation of the other.

Constraints:

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

Hints for Solving the Problem:

  1. How many ways can you rotate a string of length n?
  2. How does concatenating s + s help in checking for rotations efficiently?

Approach 1: Brute Force (O(n²))

  • Generate all possible rotations of s and check if any of them match goal.

Code (Python):

Python3
Python3

. . . .

Code (Java):

Java
Java

. . . .

Approach 2: Optimal Solution Using Concatenation (O(n))

  • Concatenating s + s contains all possible rotations of s as substrings. So, just check if goal is a substring of s + s.

Code (Python):

Python3
Python3

. . . .

Code (Java):

Java
Java

. . . .

Complexity Analysis:

  • Brute Force: O(n²) time, O(1) space.
  • Optimal (Concatenation): O(n) time, O(1) space.

Edge Cases:

  1. Empty Strings: ("", "") should return true (an empty string is a rotation of itself).

  2. Single Character: Cases like ("a", "a") should return true, while ("a", "b") should return false.

  3. Identical Strings: If s and goal are identical (and non-empty), it should return true (0 rotations needed).

Common Mistakes:

  1. Not checking if lengths differ before trying rotation logic (strings of different lengths can never be rotations).

  2. Implementing rotation incorrectly or not handling substring slicing properly for wrap-around.

  3. Forgetting that two empty strings are considered rotations of each other.

Alternative Variations:

  1. Circular Array Rotations: Similar concept but rotating an array instead of a string.
  2. Rotate Right Instead of Left: The problem could be framed by rotating to the right side, which is just a minor variation.
  1. LeetCode 796 - Rotate String: This problem itself, for reference on LeetCode.

  2. LeetCode 459 - Repeated Substring Pattern: Check if a string is composed of repeated substrings (also uses the trick of string concatenation).

  3. LeetCode 686 - Repeated String Match: Find how many times you need to repeat a string A such that B is a substring of the repeated string.

TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;