StringRotation.md

Prompt

Given two strings, write a function that returns true if one string is a rotation of the other string. In this case, a string rotation is a string that is misplaced by one cut. And example would be: "goodbye" and "odbyego" -> these are a rotation of each other.

Premise

This is very similar to other string permutation problems where checking a character count is appropriate. In this case it would not accurately get the job done, so keep that in mind.

---

Examples

isRotation("hello", "elloh"); // true
isRotation("hello", "goodbye"); // false
isRotation("hello", "lolhe"); // false

---

Possible Solution 1

This initial solution would be in the scenario where using contains, or any other built-in are not favored. There are many other ways to do this, this is just an example of one to save memory.

function isRotation(strA, strB) {
  if (strA.length !== strB.length) return false; // exit early if the strings aren't the same length
  let pin = strA[0]; // Setting a character to trace in string B
  let tries = []; // This is going to store all the indexes where the pin character shows up in string B
  for (let i = 0; i < strB.length; i++) {
    if (strB[i] === pin) {
      tries.push(i);
    }
  }

  if (tries.length <= 0) return false; // if the pin never shows up in string B, we return false

  let strAPointer = 0;
  let match = true;
  
  // Here we want to loop through strA and strB, checking to see if the order of characters and the characters themselves match.
  for (let j = 0; j < tries.length; j++) {
    while (strAPointer < strA.length) {
      if (strA[strAPointer] !== strB[tries[j]]) {
        match = false;
        break;
      }
      else {
        strAPointer++;
        tries[j]++;
        if (tries[j] >= strB.length) { // if strB is in fact a rotation, we need to accomodate for hitting the end of strB
          tries[j] = 0;
        }
      }
    }
  }
  return match; 
}

The premise here is to iterate through both strings and see if their characters are identical in the same order. This will check to see if a string is a rotation of another string.

Here we have to loop through string B initially, and then later loop through string A for as many times as there are "tries" from our string B. This essentially simplifies to a runtime of O(AB) where A is the length of string A and B is the length of string B, but since we need these strings to be the same length, we can simplify even further to O(N), where N is the length of either string.

The catch here is that it takes up more runtime, for saving possible space as we will see in the other solutions.

Possible Solution 2

Lets think of an example such as "welcome" and "comewel", which should return true if these strings are plugged into our function. If we go ahead and put two "welcome"'s together, we get a string "welcomewelcome". In fact, the second string "comewel" exists inside that combo string! Now all we have to do is just check if our second string is a substring of our combo string. Our second solution will do exactly that.

function isRotation(strA, strB) {
  // initial checks to make sure we have the apporpriate strings
  if (strA.length !== strB.length) return false;
  if (strA.length === 0) return false;

  let combo = strA + strA;
  return isSubstring(combo, strB);
}

// creating our own isSubstring method
function isSubstring(str, substr) {
  let substrIndex = 0;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === substr[substrIndex]) {
      substrIndex += 1;
    }
    if (substrIndex === substr.length) {
      return true;
    }
  }
  return false;
}

---

Now this looks much cleaner to read. Our inital function, besides the checks, is simply just two operations, adding the first string to itself, and then checking to see if strB is a substring of strA. Now the rest depends on if we are allowed to use built-in methods to check the substring, which will depend on your interviewer. In this case, we made our own, which will dictate the runtime of our function. We are looping through the combo version of strA at worst, meaning that we have to iterate through 2 tiems the length of our strA. Simplified, our runtime will also be O(N) where N is the length of either string (assuming that we terminate early if strA and strB are'n the same length).

Our space complexity here will also be double strA's length, and simplified becomes O(N) space.

The two solutions, which do look and approach very differently, actually do come out to be similar in terms of complexity.