To solve Rotate String, immediately check if the lengths match, then use string concatenation to detect all rotation possibilities. This ensures an O(n) approach by leveraging the combined string and simple substring search. Handling edge cases like identical strings or single-character inputs is crucial for correctness in interview scenarios.
Problem Statement
Given two strings s and goal, determine whether s can be transformed into goal by performing any number of left shifts. A left shift consists of moving the first character of s to the end of the string. Return true if s can become goal after some shifts, otherwise return false.
For example, given s = "abcde" and goal = "cdeab", one valid sequence of shifts can transform s into goal. Ensure your solution works efficiently for all strings up to length 100 and considers only lowercase English letters.
Examples
Example 1
Input: s = "abcde", goal = "cdeab"
Output: true
Example details omitted.
Example 2
Input: s = "abcde", goal = "abced"
Output: false
Example details omitted.
Constraints
- 1 <= s.length, goal.length <= 100
- s and goal consist of lowercase English letters.
Solution Approach
Concatenate and Search
Concatenate s with itself to capture all rotation possibilities and then check if goal is a substring. This uses the string plus string matching pattern directly and avoids manual shift simulation.
Length Check Early
Immediately return false if s and goal have different lengths. This simple step avoids unnecessary computation and aligns with the problem's failure mode when lengths mismatch.
Use Efficient Substring Search
Leverage built-in substring search methods for O(n) detection of goal within s+s. Avoid nested loops to prevent O(n^2) complexity and focus on the exact rotation pattern.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Time complexity is O(n) due to concatenation and single substring search. Space complexity is O(n) to store the doubled string. Edge cases like identical strings or single-character strings do not change this bound.
What Interviewers Usually Probe
- Look for recognition that concatenating s with itself captures all rotations.
- Check if candidate handles edge cases like empty strings or single-character strings.
- Watch for inefficient nested loops that simulate every shift explicitly.
Common Pitfalls or Variants
Common pitfalls
- Simulating each rotation with loops instead of concatenation causes unnecessary O(n^2) time.
- Forgetting to compare lengths before processing leads to false positives.
- Assuming only one shift is required instead of considering all rotations.
Follow-up variants
- Check rotations allowing both left and right shifts to extend the basic pattern.
- Find the minimal number of shifts needed to reach the goal string.
- Apply the string plus string matching pattern to circular arrays or lists instead of strings.
How GhostInterview Helps
- GhostInterview quickly identifies the rotation pattern and confirms substring matches efficiently.
- It highlights failure modes such as mismatched lengths or overlooked edge cases.
- The solver guides step-by-step through concatenation and substring checks, ensuring correct O(n) execution.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the most efficient way to check rotations in Rotate String?
Concatenate s with itself and check if goal is a substring. This captures all rotation possibilities in O(n) time.
Do I need to simulate each shift manually?
No, manual simulation is inefficient. Using s+s avoids nested loops and directly leverages string matching.
Can Rotate String handle empty or single-character strings?
Yes, the approach works correctly for these edge cases since substring checking and length comparison handle them naturally.
Why is the length check important before substring search?
If s and goal lengths differ, no rotation can succeed. Checking early avoids wasted computation and false positives.
Does this pattern apply to arrays or lists?
Yes, the string plus string matching pattern can extend to circular arrays, where concatenation and element comparison replace substring search.
Need direct help with Rotate String instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Rotate String from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the minimum number of repetitions of string a to make string b a substring of the repeated string a.
Open problem page#1023 Camelcase MatchingCamelcase Matching is a medium difficulty problem where you match queries to a given pattern by inserting lowercase letters.
Open problem page#459 Repeated Substring PatternCheck if a string can be constructed by repeating a substring using string matching techniques.
Open problem page