Rotate String: How to solve using the includes method

Using only one call with the includes method, how we can cleverly solve this algorithm question in just two short lines of JavaScript code

In a recent mock technical interview, I was presented with an interesting coding exercise that asked me to compare two string inputs & whether one string is a “rotated” string of the second string. The question was stated as follows:

Note that this problem is also on Leetcode (question #796). Link to the question: https://leetcode.com/problems/rotate-string/

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

So we either return true or false depending on whether A can become B after some number of shifts on A. Order matters here, so how can we implement an efficient solution?

As I was speaking with my interviewer, my initial thought process was to tackle this with a brute force approach (I have been going to the gym, after all!).

Note: If you’d like to skip this part & jump to the “includes” approach, that approach will be under the “Clever Approach” heading

Brute Force Approach

Looking at the problem, I immediately thought of mutating the inputs with each iteration. With each iteration, if we can remove the last character & add it to the beginning, we can check to see whether it equals the second string. If it’s the same, we return true & break out of our loop. If not, we continue.

Want to read this story later? Save it in Journal.

One valuable lesson I learned here was that strings are immutable, so if we wanted to implement this approach, we would have to turn our strings into something that we can alter (an array).

So let’s write our game plan & see how it would look in plain English:

1. Convert A string into an array by using the built-in split method. Set it o a variable called Aarray
2. Set a variable equal to the length of Aarray -> Remember, because we’re altering the array with each iteration, our lengths will get shorter, so we need to make sure we have the loop iterate the number of times we expect to.
3. Set up a for loop that iterates over the length of Aarray -> using the pop method to remove the last character & the unshift method to add that character to the beginning of the string
4. At the end of each loop, convert the array back into a string using the join method & compare it to B. If it’s equal, return true

Here’s how our code would look:

Note that to pass all the test cases on Leetcode, there was one case where both inputs were an empty string. The edge case was addressed prior to entering the loop.

So there’s our brute force approach. While it’s not the sexiest approach, we do get the result that we need in a quadratic (O N²).

However, there is a more clever approach that I wanted to introduce to you all, and that’s calling the includes method.

This might just blow your mind!

Clever Approach

So think about this — we’re comparing two strings and checking to see whether one string is a “rotated” version of another string.

What if we took string A & added it to itself?

Let’s look at an example. Say our example strings are as follows:

String A: “waterbottle”
String B: “erbottlewat”

Now let’s create a new string where we add String A to itself. Our new string would look like this:

New String: “waterbottlewaterbottle”

Notice that with this new string, we can now check to see if it includes (any) rotated strings! Using our example above:

New String: “waterbottlewaterbottle”

Boom! There’s our string!

So how would this look in code? Well, it’s quite simple, actually!

1. We need to create a new string that adds A to itself. We can use the concat method here
2. Call our includes method on our New String and pass in the B string. The includes method checks to see whether its passed in parameter is included in the object that it’s called on. It immediately gives us an output of true or false

How’s that for a brain teaser? Big shout out to my interviewer Andy for introducing this to me.

Conclusion

There is nothing more humbling to come across a solution that is 10x more efficient than yours. There are some clever people out there, but each time I do get taken to school, it reignites my drive to understand these concepts more & hopefully come up with something clever myself one day.

Let me know your thoughts on this approach or if you have another clever approach you’d like to share!

Until next time.

📝 Save this story in Journal.