Justin Ho

Posted on Oct 7, 2020 • Edited on Oct 19, 2021 • Originally published at jcsh.dev

The Scrabbling String Problem

I got a chance to solve a "whiteboard" question (a jargon for data structures and algorithms question done on a whiteboard usually at interviews) the other day and wanted to break it down for anyone who might come across this in their interviews. This was labelled medium difficulty on the website.

The Whiteboard Question

Given 2 strings, wordToBeFound and lettersInHand, return true if the characters in lettersInHand can be arranged to form wordToBeFound and false if it cannot.

A Sample Output

lettersInHand = "heulselo";
wordToBeFound = "hello";
console.log(canScrabbleString(wordToBeFound, lettersInHand));
// returns true because lettersInHand contains "h", "e", "l", "l", "o"

Approaching Whiteboard Problems

Depending on your experience, this can either completely freak you out or you just let out a sigh of relief for how easy it is.

If you're freaking out, the first thing I'd do is stop, take a breath, and read the question a second time.

Do not start writing an answer, especially if you're freaking out.

Next step is to talk (and write) out your thought process. Ask yourself what are your known variables? What's the challenge here?

For this question, I noted that I have 2 string variables and it didn't matter if either are null or empty as I'm returning a boolean. Next, I noted that the challenge was identifying if a character existed x number of times in lettersInHand as there are in wordToBeFound.

Next I translated my rough idea into pseudo code

For each letter in wordToBeFound, search lettersInHand for a corresponding letter
If a matching letter is not found, return false
If a matching letter is found, remove the letter to track duplicates
If every letter has been found return true

First Pass - Minimal Viable Code

So I've analyzed the problem and identified a solution. It could be wrong. But if the interviewer doesn't stop to correct you, don't second guess yourself right now.

On my first attempt, I try to simplify the problem and my solution. For example, I'll assume there are no duplicate letters and that there's at least 1 letter in each string, and I will not try to optimize for complexity; I found myself not being able to come up with a solution when I attempt to solve the bigger problem and optimize for complexity right from the get-go.

Assuming no duplicates, I came up with a naive solution using a nested for loop.

/*
 * Determines if characters in lettersInHand can be used to form wordToBeFound
 * Time complexity - O(n^2)
 * 
 * @param {string} wordToBeFound - not null string with no duplicate letters
 * @param {string} lettersInHand - not null string
 */
function scrambleString(wordToBeFound, lettersInHand) {
  for (let wordIndex = 0; wordIndex < wordToBeFound.length; wordIndex++) {
    let stringFound = false;
    for (let letterIndex = 0; letterIndex < lettersInHand.length; letterIndex++) {
      if (wordToBeFound[wordIndex] === lettersInHand[letterIndex]) {
        stringFound = true;
      }
    }
    if (!stringFound) return false;
  }
  return true;
}

You do not have to use long for-loop variable names, I used i and j as the for-loop variable names for my actual submission but I changed it up to make it clear here.

Next, you should either manually test it (if you're actually on a whiteboard) or test it in a browser (advantage of using Javascript) or web editor.

Since this is an initial solution, I just came up with some inputs that I knew the output for.

Example:

console.log("should be true - result: " + scrambleString("helo", "heklio"));
console.log("should be false - result: " + scrambleString("fairy", "level"));
// Output:
// should be true - result: true
// should be false - result: false

Second Pass - Solves the Problem

Now that this solution works for a simple case, we can move on to accounting for duplicate letters. A simple approach is to just remove the letter from the string when it's matched. Since our function will return false once there are no more copies of the letter, the function should still work.

...
      if (wordToBeFound[wordIndex] === lettersInHand[letterIndex]) {
        stringFound = true;
        // ==================================
        // remove the character found from the string
        lettersInHand = lettersInHand.replace(lettersInHand[letterIndex], "");
        // ends the inner for-loop to prevent removing additional characters 
        // or out of bounds error
        break; 
        // ==================================
      }
...

How To Make The Solution Better

This next step might trip some beginners up because they are either not sure what to do next or not sure how to proceed to the next step.

In my opinion, after you have a working solution, there are only 3 distinct categories for improvement at this point that is useful to the interview:

code quality - code structure, consistent name casing and tense, useful comments
efficiency - the "Big O"
handling errors - catching nulls or undefined, incorrect type

What you choose to prioritize and how you go about it will depend on time constraints and your ability as a developer.

In this problem, I will only demo improvement of the efficiency in my solution.

Time Complexity

In case you do not know about time complexity, it's a metric to measure the time it takes for an algorithm to complete. I won't go in depth here but basically our first solution has a time complexity of O(n^2) because we have a nested for-loop that has no other complex operation inside. The loops iterate over the first string s1.length times but iterate over the second string s1.length * s2.length times. Since Big O notation usually account for worst case, we use the inner measure and take all input as n, we get n*n or n^2.

Trading Memory for Speed

A common way to make your algorithms more efficient is to use a suitable data structure. There are many different data structures and arrays are by far the most known one. Arrays are space efficient and everything is ordered, but it's not very efficient for searching a known value. Instead, there are more search efficient alternatives such as hash tables or binary trees which should be easy enough to implement in an interview setting.

For this problem, I have the luxury of using the native hash table equivalent in Javascript: Map.

You can search up how to implement your own hash table in Javascript afterwards so I'll just show my final solution.

My Final Solution

/*
 * Determines if characters in lettersInHand can be used to form wordToBeFound
 * Time complexity - O(n)
 * 
 * @param {string} wordToBeFound - not null string with no duplicate letters
 * @param {string} lettersInHand - not null string
 */
function scrambleString(wordToFind, lettersInHand) {  
  let stringMap = new Map();

  for (let index = 0; index < lettersInHand.length; index++) {
    if (stringMap.has(lettersInHand[index])) {
      let copies = stringMap.get(lettersInHand[index]) + 1;
      stringMap.set(lettersInHand[index], copies);
      continue;
    }
    stringMap.set(lettersInHand[index], 1);
  }

  for (let index = 0; index < wordToFind.length; index++) {
    if (!stringMap.has(wordToFind[index])) {
      return false;
    }
    let copies = stringMap.get(wordToFind[index]) - 1;
    if (copies === 0) stringMap.delete(wordToFind[index]);
  }

  return true;
}

The reason this is more efficient is because the Map object in Javascript has an average retrieval of O(1) compared to using a loop to search for the value in an array (O(n)). By breaking the nested loops, we have improved the worst-case complexity to O(n).

Wrapping Up

Thanks for reading! I hope you learned more about answering whiteboard questions today.

To be quite honest, I still struggle at them and I am only this confident after going back to review what I did wrong so don't feel discouraged if this stumped you or you felt like you can't do this.

Instead, I challenge you to go try solving a whiteboard question on any website!

Let me know if you have any suggestions in the comments below.

Follow me on Twitter @justinhodev if you want to keep up with my daily coding!

Bonus

So if any reader is familiar with JavaScript functions, they may have looked at String.indexOf() instead of a nested for-loop in my first or second solution. I couldn't find any reference for its time complexity but I will assume it's the same as Array.indexOf() and based on this source (and its corresponding links), it's just a cleaner syntax but the implementation is still a for-loop so the complexity should still be O(n^2). If you happen to know the answer, let me know in the comments!

Top comments (5)

Peter Vivo • Oct 7 '20

Nice, but functional thinking maybe give shorter result:

My first try

[..."hellwallelalheulselo"].filter(c => "hello".includes(c))
// result: ["h", "e", "l", "l", "l", "l", "e", "l", "l", "h", "e", "l", "e", "l", "o"]

lead to me loop wordToBeFound instead of lettersInHand

const canScrabbleString = (lettersInHand, wordToBeFound) => -1 < 
  [...wordToBeFound]
    .reduce( (cursor, chr) => lettersInHand.indexOf(chr, cursor), 0);

Justin Ho • Oct 7 '20 • Edited

Thanks for comment Peter!

Yes I did not believe my solution was the most elegant one so I'm glad you provided a functional one!

I'll have to familiarize myself more with higher order functions.

Peter Vivo • Oct 7 '20

funfunfunction reduce the swish knife of coding.

Grzegorz Kućmierz • Oct 7 '20 • Edited

What do you think about this solution?

const canScrabbleString = (word, letters) => {
  const map = new Map();

  [...letters].map(char => {
    const count = map.get(char) ?? 0;
    map.set(char, count + 1);
  });

  for (let i = 0; i < word.length; ++i) {
    const char = word[i];
    const count = map.get(char) ?? 0
    if (count <= 0) return false;
    map.set(char, count - 1);
  };

  return true;
};

const lettersInHand = "heulselo";
const wordToBeFound = "hello";

console.log(
  canScrabbleString(wordToBeFound, lettersInHand)
);