Check if string s can become goal after any number of rotations.
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 on `s` consists of moving the leftmost character of `s` to the rightmost position.
Examples
Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: Goal string can be obtained by shifting characters of s.
Input: s = "abcde", goal = "abced"
Output: false
Explanation: Goal string cannot be formed by shifting characters of s.
Complexity
Time Complexity: O(N)
Space Complexity: O(N)
Hints
š” Hint 1:
Any rotation of s will always appear as a substring of s + s.
š” Hint 2:
First check if s and goal have identical length.
š” Hint 3:
Return s.length === goal.length && (s + s).includes(goal).
Editorial & Approach
Problem Overview & Intuition
Concatenating s with itself (s + s) contains every cyclic shift of s of length N. Therefore, goal is a valid rotation of s if and only if lengths match and (s + s).includes(goal).
Step-by-Step Approach
- Check if
s.length !== goal.length; if so, returnfalse. - Return
(s + s).includes(goal).
Optimal Implementation (JavaScript)
function rotateString(s, goal) {
if (s.length !== goal.length) return false;
return (s + s).includes(goal);
}Complexity Analysis
Time Complexity
O(N) ā string search in 2N length string.
Space Complexity
O(N) ā memory for concatenated string.
Edge Cases & Corner Traps Handled
- Different length strings: returns false.
- Identical strings: returns true.
- Single character match/mismatch.