Rotate String

Easy
234.

Rotate String

Rotate String is an easy coding problem on strings and string matching, asked in Amazon, Google and Microsoft interviews.

Given two strings s and goal, return true if s can become goal after some number of left shifts.

A left shift moves the leftmost character to the end of the string.

Example 1

Input
s = "abcde", goal = "cdeab"
Output
true
Explanation
Two left shifts.

Example 2

Input
s = "abcde", goal = "abced"
Output
false

Example 3

Input
s = "a", goal = "a"
Output
true

Constraints

  • 1 <= s.length, goal.length <= 40
  • Both consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function(s, goal) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rotate String — Solution in Python, Java & C++

Rotate String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.

Rotate String is an easy coding problem on strings and string matching, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Strings, String Matching
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two strings s and goal, return true if s can become goal after some number of left shifts.

A left shift moves the leftmost character to the end of the string.

Example 1

Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: Two left shifts.

Example 2

Input: s = "abcde", goal = "abced"
Output: false

Example 3

Input: s = "a", goal = "a"
Output: true

Constraints

  • 1 <= s.length, goal.length <= 40
  • Both consist of lowercase English letters.

Hints for Rotate String

  1. Hint 1

    Every rotation of s appears as a contiguous substring of s + s.

  2. Hint 2

    So the answer is just a length check plus a substring search.

  3. Hint 3

    Do not skip the length check — "a" is a substring of "abab" without being a rotation of "ab".

How to solve Rotate String

Every rotation of s is a substring of s + s, so check the lengths and search.

Approach

  1. Return false if the lengths differ.
  2. Return whether goal occurs in s + s.

Why it works

s + s contains each left shift of s as a window of length n starting at offsets 0..n-1, and a same-length substring of it must be one of those windows.

Complexity

  • Time — O(n) with a linear substring search
  • Space — O(n)

Pitfalls

  • Skipping the length check lets "a" match inside "abab".

Reference solution

Python

def rotateString(s: str, goal: str) -> bool:
    return len(s) == len(goal) and goal in s + s

Java

public static boolean rotateString(String s, String goal) {
    return s.length() == goal.length() && (s + s).contains(goal);
}

C++

bool rotateString(string s, string goal) {
    return s.size() == goal.size() && (s + s).find(goal) != string::npos;
}

JavaScript

var rotateString = function(s, goal) {
    return s.length === goal.length && (s + s).indexOf(goal) >= 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings