Paul Coroneos

Today we will be talking about Cracking the Code Interview 1-9 which covers string rotation.

As always let's start with the prompt:

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings S1 and S2, write code to check if S2 is a totation of S1 using only one call to isSubstring.

Now to be honest this was a little bit scary to me first. Effectively if we try to distill this problem down it is asking us to check whether given one word that the other word is the same word as the first but just with a few characters rotated around. Makes sense? (no? 😊) Okay let's look at an example

Suppose we have the word peacemaker. We print it out on a piece of paper like so:

|p|e|a|c|e|m|a|k|e|r|

We then take a pair of scissors and cut between the e and m like so:

|p|e|a|c|e| |m|a|k|e|r|

We then take the piece called maker and place it front of the first piece.

|m|a|k|e|r|p|e|a|c|e|

This is what the problem calls a "rotation" and our function would return true. Now that we understand what the problem is asking how would we tackle this problem?

Approaching the problem.

In a lot of these array problems we have discussed so far the ever trusty hash table is a trusty tool to reach for. In fact when I approached this problem that was the first thing I considered. So in psuedocode this was my initial thinking

// make a hashtable of first world keyed by each letter and how many times it appears

//iterate through that hash table and then validate that at least each letter exists in the first string.

// return true if the hash table finishes empty

Now this actually works IF we are trying to validate both words contain the same letters. But actually it might be just easier to sort each array then compare both resulting strings. And in any case this doesn't actually meet the critera of the problem for two reasons

The order of the letters cannot change. Only the "starting point" of the word in the sequence. The above code doesnt check that
This approach doesnt use isSubstring at all which is clearly really important information.

So after ripping up a sheet of paper and throwing it into the trash 🗑️ I rethought the problem.

Approaching the problem (again)

What does isSubstring actually do? Well most languages have a version of this method in their string prototype but essentially a substring is just literally a piece of a larger string. So therefore isSubstring would check whether a piece of a string is part of a bigger string. Now armed with this hint lets look at our word again:

S1 |p|e|a|c|e|m|a|k|e|r|

S2 |m|a|k|e|r|p|e|a|c|e|

How can we use the above to solve our problem? Well it turns out there's a pretty clever trick we can use. We know again S2 must be a rotation of S1 meaning that while the order of the letters can be different they must be in the same sequence (cannot be randomly scrambled). In the case of S2 we can visually see in this example the word has simply been bisected in two and shuffled. Well what if we actually just create a new string that is two copies of the first string joined together?

S3 |m|a|k|e|r|p|e|a|c|e|m|a|k|e|r|p|e|a|c|e|

It might be hard to see now but what should stand out to you is the word peacemaker is actually right in the middle. And what did the problem saw we were provided? A function isSubstring(). And thats the trick. **We simply concatenate two copies of the second string together then see if substring S1 exists in new string S3

Implementation

The implementation is thus very simple.

//use JS string.Prototype.inclues() to implement isSubstring()
const isSubstring = (concatStr: string, strb: string) =>
  concatStr.includes(strb);

const stringRotation = (stra: string, strb: string) => {
  //base case. Strings need to equal sized and at least greater than length 0
  if (stra.length === 0 || stra.length !== strb.length) return false;
  const concatenatedStr = `${stra}${stra}`;
  return isSubstring(concatenatedStr, strb);
};

I went ahead and wrote my own isSubstring implementation using includes() in the case. But there are many ways such a function could be implemented. Effectively we first check to see whether the string are equal length and at least string a is not length 0 for a bit of error checking. Then I simply use a JavaScript template literal to concatenate the two strings together. Finally I call my isSubstring method to determine whether it is a valid rotation

Complexity analysis

We are going to need to search the whole string worst case to find a substring. So at minimum this is yet again O(n). This aligns with the complexity of most search like problems.

Thank you and as always best of luck studying algorithms!