GitHub repo with completed solution code and test suite.

What is the Ransom Note challenge?

‘Given two strings:

1. A source string, i.e. the “page”

2. A desired string, i.e. the “note”

determine if the desired “note” string can be created using only the letters found in the source “page”.’

A visual example of what we’re looking for would be this:

So, if we had a page of text, we could chop it up into all its separate letters, then glue them onto a new page to form a new word or phrase of our choosing.

Ok, so let’s get started!

I like to start with a little bit of pseudocode, just so I can write out my aims in a programming context.

let canMakeNote = (source, note) => {
    if (source contains all the letters needed to make note){
      return true
    }else{
      return false
    }
}

So here we have a function called canMakeNote, whose job is to see if the source string contains all the letters needed to create the desired note string. If that is true, it should return true, and if not, false.

However, “if source contains all letters needed to create note” is doing a lot of heavy lifting in the above pseudocode. Let’s start at the beginning.

We know one thing right away: If the source string is shorter than the note string, we will not be able to make the note. There’s no way that we’ll have all the letters we need.

So first things first, we’ll need to compare the length of our two strings. If the source string is too short, we won’t need to bother with anything else, and can immediately return false.

However, strings can be… messy.

They could include whitespaces, which I’m not going to track as if they were a letters — if I were cutting letters out of a newspaper or magazine and gluing them onto paper, I wouldn’t cut out and paste on spaces. Counting each whitespace as a letter could be an interesting variation of this challenge, but I’m not going to explore that in this solution.

So, if whitespaces don’t count as letters, they’ll distort our ability to measure the length of our strings. Not good.

Plus, the strings might contain both capital and lowercase letters. This won’t affect our judgement of the length of the strings, but it will become an issue further down the line when we begin attempting to compare the content of the strings. For our purposes, “A” is the same as “a”. After all, the iconic ransom note is defined by its higgledy-piggledy mix of upper and lower cased letters. The computer, on the other hand, sees “A” and “a” as completely different characters.

So that gives us two things we’ll need to account for as we compare our input strings, whitespaces and character case.

**Note: Some variations of this challenge will provide the input and desired output parameters in the form of arrays of letters, all tidy and ready to go. That’s great! If you run across a challenge like that, you can just skip this step! However, I wanted to provide a solution that accounts for input / desired output in string form.

To clean up our messy strings and transform them into something more convenient to our purposes, let’s make a helper function.

I’ll need to account for the whitespaces and character case, and, as this is an algorithmic challenge, I’m going to go ahead and transform our strings into arrays, so that each character will be individually separate, and our data will be in a convenient form for iteration, manipulation, and comparison.

First, I’ll pseudocode it out:

let clean = (input) => {
  remove whitespaces from input
  lowercase input
  transform input into an array
  return the cleaned & transformed input
}

So we’ve got a handy list of what our string cleaning helper function needs to do.

First, the whitespaces.

Whenever I need to identify and manipulate a certain character or characters in a string, I think of RegEx. RegEx is the shorthand reference for a“Regular Expression”. What is a that?

RegEx

A regular expression, regex or regexp (sometimes called a rational expression) is a sequence of characters that define a search pattern. Usually such patterns are used by string searching algorithms for “find” or “find and replace” operations on strings, or for input validation.

What can RegEx search patterns do? They’re great at collecting all the characters in a string that match a given search criteria, then collecting or manipulating them as directed. This can be incredibly handy, making things that would otherwise be laborious and complicated relatively quick. The tradeoff is that performing RegEx find and replace operations can be computationally expensive! Which should be considered when RegEx is being considered for manipulating extremely large strings. However, for our purposes at this time, RegEx is just what the doctor ordered.

I’ll be honest, I’m not an expert who’s memorized all the different RegEx patterns and their meanings. I know enough to be able to quickly recall my most-used patterns, but mostly, I’ve had great success with just developing the ability to identify when I’m looking at a problem that would be eased by the use of RegEx. Then, a quick google of the type of find and replace operation I want to perform with the keyword “RegEx” and perhaps the language of the code I’m currently writing usually yields results within the first few links.

In this case, I googled “javascript regex remove all whitespaces from string” and was promptly provided with the appropriate RegEx pattern for my needs.

OK, enough about RegEx! Back to our string-cleaning helper function.

I can combine Javascript’s ***replace*** method with my chosen RegEx pattern, to replace every whitespace in my string with nothing, therefore stripping them out entirely. The RegEx search pattern that I chose also removes line breaks, and any other sorts of “blank” characters it might encounter.

let clean = (input) => {
  input.replace(/\s/g,'')
  lowercase input
  transform input into an array
  return the cleaned & transformed input
}

input is the name of our argument, which can be any string passed into the function. /\s/g is the RegEx search pattern to identify all whitespaces / blank characters, and the empty string that follows tells **input.replace **that we want to replace the whitespaces with nothing. Altogether, this combo will strip all the blank characters from our input string.

Whitespaces handled. ✔️

Next on our list is character case.

Lucky for us, Javascript comes complete with its own ***toLowerCase*** method, which does pretty much what it says on the tin. When called on a string, it will transform all capital letters in the string to lowercase letter. So, our **clean* *function can accomplish the next task on our pseudocode list by calling this method.

let clean = (input) => {
  input.replace(/\s/g,'').toLowerCase()
  transform input into an array
  return the cleaned & transformed input
}

Okay, finally, we want to change our stripped and lowercased string into an array of characters, and return the final result.

Again, Javascript has the relevant method ready and waiting for us, as this is the exact purpose of the ***string.split()*** method. We have to tell the method where we want it to split the string, which we can do by including the trigger character in quotes within the parentheses after the method name. However, as we want to separate out each individual character (rather than splitting at each space, for example, to separate out words, or at final punctuation marks to separate sentences), we put nothing inside the quotes.

So, our final clean function looks like this:

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

While the GitHub repository for this article includes a testing suite, I also like to use the browser console to quickly check my functions and make sure they’re returning what I want. Let’s see what this clean function returns when given a quote.

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

let quote = "Aut Viam Inveniam Aut Faciam"

clean(quote)

> (24) ["a", "u", "t", "v", "i", "a", "m", "i", "n", "v", "e", "n", "i", "a", "m", "a", "u", "t", "f", "a", "c", "i", "a", "m"]

🌟 Great! This is exactly the result we wanted. We now have a cleaning function that can take in a string, downcase any capitals, remove all whitespaces, and return a handy array ready to go for our comparison needs.

In order to effectively compare our now-transformed strings, we need to track two data elements: the individual characters that we either have available or need, and also frequency with which each character we either have available or need occurs.

The source text may, for example, contain the letter “e” — but what if our desired output text needs five “e”s? An instance of a matching letter alone is not enough to decide that the source text has what we need.

In Frequency Analysis, this is a routine challenge, which is often met with the use of Histograms, which are quite similar to Bar Charts.

These graphical tools are a visual representation of the exact two pieces of data we need to track — letter and frequency of occurrence.

Now, unfortunately I can’t simply show a histogram to my computer. However, I can use a non-graphical data structure to communicate the same information that’s in my histogram.

Speaking of Data Structures, the more algorithms I solve, the more I appreciate the Hash Table. The data structure that allows the storage of key-value pairs is often an effective and efficient tool in tasks that require comparing lots of little bits of data. If you’d like to see another example, my set of solutions to the Two Sum Problem includes a hash-based solution, which is by far the most efficient of the three solutions I explore.

So when I see a challenge that requires the storage of paired pieces of data, it feels intuitive to at least try storing those pieces of data as key-value pairs.

Let’s pseudocode out this specific task, just as we’ve done before:

let makeHistogram = (input) => {
    let histogram = {}

    assign each letter of input to a key in histogram
    assign the occurrence frequency of that letter to the corresponding value

    return histogram
}

So we’re setting out to create a hash object which can mimic a frequency occurrence histogram. In it, we want to save each character to a key, then store that character’s occurrence frequency (the number of times it’s repeated) to the value attached to that key.

Since we’re needing to check each letter, we should start by iterating through our input. I’m assuming the input is an array of relevant lowercase characters, as that’s what our previous clean helper method returns.

For each letter, I’ll need to determine if we’ve already encountered it before. If it’s the first instance of that letter in the array, we need to make a new key in our histogram hash object, and assign it the value 1, for one occurrence. If the letter has occurred earlier in the array and therefore has already had a key created for it, we should not make a new key, but rather add 1 to the existing key’s value.

So, with a bit more pseudocode, we can sketch out our loop structure:

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        if the letter has been encountered before,increment the value of the key corresponding to letter by one 
        else create a key for it and assign a value of one
    }  
    return histogram
}

As I only have two behavior patterns to choose from, I can write out the conditional statement for this using a ternary operator.

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        letter in histogram ? histogram[letter] += 1 : histogram[letter] = 1
    }  
    return histogram
}

In this code, the section before the ? is the if statement. This is what we’re checking for as we iterate through the input array — for each letter of input, we’re checking to see if it already exists in histogram. If it does, the first operation which comes right after the **? *(adding one to the value which corresponds to the letter’s key) should be performed. Otherwise, the second operation which comes after the *: **(creating a key for the letter and assigning it a value of one) should be performed.

Just as we did with our clean helper function, let’s throw this into the console and see what it outputs.

let quote = "Aut Viam Inveniam Aut Faciam"

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

let cleanedQuote = clean(quote)

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        letter in histogram ? histogram[letter] += 1 : histogram[letter] = 1
    }  
    return histogram
}

makeHistogram(cleanedQuote)

> {a: 6, u: 2, t: 2, v: 2, i: 4, m: 3, n: 2, e: 1, f: 1, c: 1}

🌟 Great! This returns a hash object containing each letter from the given input as a key, and the occurrence frequency of that letter as the corresponding value.

We’ve now organized our data into a structure that we can efficiently test. Enough with the helper functions, we’re finally ready to do something with the very first pseudocode function we wrote!

let canMakeNote = (source, note) => {
    if (source contains all the letters needed to make note){
      return true
    }else{
      return false
    }
}

So this was our original pseudocode.

First things first, we know we’ll be returning a boolean. Let’s go ahead and create a variable for that return value — I’m going to call it boolean for ease and give it a default value of false.

Then, we can use our clean function to clean up our input.

That will give us two arrays, the lengths of which we can compare. That way, just as we originally stated, if the source is longer than the note, we’ll want to move forward, but if it’s not? We don’t need to do anything else and can immediately return false. Since we initialized our boolean variable with a value of false, we can just return it.

Thus far, we could write that out like this:

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        use histogram to see if source contains all the letters needed to create note
    }
    return boolean
}

This is much closer to a working function than the pseudocode we started with, but there’s still a big vague chunk in the middle.

That’s okay though, that’s what our makeHistogram function is for!

We can call makeHistogram twice, inputting our cleaned arrays, and get two hash objects, which we can now compare.

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        let sourceHistogram = makeHistogram(source)
        let noteHistogram = makeHistogram(cleanedNote)
        for(let letter in noteHistogram){
            if (the value of the key letter in sourceHistogram is greater than or equal to the value of the key letter in noteHistogram){
                boolean = true
            } else {
                boolean = false 
                break
            }
        }
    }
    return boolean
}

There’s still a bit of pseudocode standing in, but we can now iterate through the keys of the cleaned & hashed note text, and check each one against the cleaned and hashed source text. As a hash key provides a specific place in memory to directly check, this is a very efficient way to compare these pieces of data.

As we iterate through the note object, if the check against the source object reveals that it contains the correct character in the correct amounts, the boolean should be assigned the value true. If this check fails, the boolean should be assigned the value false and we can use the ***break*** statement to immediately exit the for loop, which will trigger the boolean return, thus causing our function to return false.

However, if each character key checked returns true, the for loop will resolve with the boolean still assigned the value true, then and only then will our function return the value true.

All that’s left to do then is to write the code for testing the values of the hash objects.

We need to check for two things:

1: That the source hash object has a key matching the current letter.

2: If true, that the corresponding value is greater than or equal to the value of corresponding to the current letter key in the note hash object.

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        let sourceHistogram = makeHistogram(source)
        let noteHistogram = makeHistogram(cleanedNote)
        for(let letter in noteHistogram){
            if (sourceHistogram[letter] && sourceHistogram[letter] >= noteHistogram[letter]){
                boolean = true
            }else{
                boolean = false 
                break
            }
        }
    }
    return boolean
}

Okay, this looks promising, let’s throw everything into the console and see what we get.

let quote = "Aut Viam Inveniam Aut Faciam"

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        letter in histogram ? histogram[letter] += 1 : histogram[letter] = 1
    }  
    return histogram
}

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        let sourceHistogram = makeHistogram(source)
        let noteHistogram = makeHistogram(cleanedNote)
        for(let letter in noteHistogram){
            if (sourceHistogram[letter] && sourceHistogram[letter] >= noteHistogram[letter]){
                boolean = true
            }else{
                boolean = false 
                break
            }
        }
    }
    return boolean
}

// let's try a word that only needs letters contained within our quote
canMakeNote(quote, "acuminate")

true

// okay, now a word that requires one more letter "e" than our quote possesses
canMakeNote(quote, "cuneate")

false

🌟 Great!

I really love this algorithm challenge because I think it’s a perfect use case for one of my favorite algorithm-solving tools, the humble hash. I hope this solution illustrates how useful a hash table can be, and that this approach is helpful to all your algorithm-solving challenges!