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:

Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: "abcde" can be rotated to "cdeab" after 3 shifts.
Input: s = "abcde", goal = "abced"
Output: false
Explanation: No possible rotation of "abcde" results in "abced".
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:

How many ways can you rotate a string of length n?
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

. . . .

Code (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

. . . .

Code (Java):

Java

. . . .

Complexity Analysis:

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

Edge Cases:

Empty Strings: ("", "") should return true (an empty string is a rotation of itself).
Single Character: Cases like ("a", "a") should return true, while ("a", "b") should return false.
Identical Strings: If s and goal are identical (and non-empty), it should return true (0 rotations needed).

Common Mistakes:

Not checking if lengths differ before trying rotation logic (strings of different lengths can never be rotations).
Implementing rotation incorrectly or not handling substring slicing properly for wrap-around.
Forgetting that two empty strings are considered rotations of each other.

Alternative Variations:

Circular Array Rotations: Similar concept but rotating an array instead of a string.
Rotate Right Instead of Left: The problem could be framed by rotating to the right side, which is just a minor variation.

LeetCode 796 - Rotate String: This problem itself, for reference on LeetCode.
LeetCode 459 - Repeated Substring Pattern: Check if a string is composed of repeated substrings (also uses the trick of string concatenation).
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