JavaScript Problem Solvers: Instagram Stickers

CASE 001: Making a Ransom Note

I was given this problem as a code challenge while applying for Facebook’s Discover Production Engineering Program. I really struggled to find a solution within the amount of time given. Afterwards, I quickly realized I needed to improve my technical problem solving skills and get on that LeetCode grind.

I also got the idea to write blogs on some of the more interesting problems I come across and solve, with the Instagram Stickers being the one that started it, making it a good problem to begin with.

So let’s get solving.

THE PROBLEM

I am at a carnival, and I found a stand that sells Instagram stickers. I want to see how many stickers I would need to buy in order to create a phrase or word. The phrase I want to create only contains letters from the stickers I can buy.
For instance, I would need to buy 2 stickers in order to create the phrase ‘artisan martians,’ 3 stickers to create the phrase ‘taming giant gnats’ and 1 sticker to create the word ‘tiara’.

THE BREAKDOWN

To start off, the problem doesn’t follow the usual HackerRank or LeetCode formula and doesn’t give us constraints with test cases and explanations, so we kind of have to make do with what we have.

First, let’s break down the problem into some language that is easier to digest and make sure we understand it:

Return the minimum amount of times the string ‘instagram’ would need to be repeated to create a given string.

I think that is a bit easier to understand, and helps us figure out where to start.

The first idea that comes to my mind is to loop through the given string and build an object that keeps count of the characters in the string.

Then, loop through the object of character frequencies and keep a running count of the character that appears the most.

We want to find the character that appears the most because the character that appears the most is also the least amount of stickers we have to buy to create the phrase given to us.

This is because the word instagram consists of singular characters except for the letter a , which appears twice. For example, if we want to create the phrase nmmmmmns we would need to buy 6 Instagram stickers, since the word instagram only contains 1 m , and the phrase contains 6 m’s .

The catch is if we have a phrase that has more than two a’s. For instance, the phrase mans would only need 1 sticker. The phrase maans would still only need 1 sticker, since the word instagram has two a’s in it.

But if we have the phrase maaans we would now need 2 stickers, since the phrase has 3 a’s. The phrase maaaans would still only need 2 stickers, but the phrase maaaaans would need 3 stickers and so on.

The way we can to solve this is by dividing the amount of times a appears in the given string by 2, and round the dividend up to the nearest integer. Since we are going to be using the values in an object to determine the maximum amount of instagram stickers we will need to buy, we are going to get a disproportionate amount of a’s in the object.

We can adjust for this when we are looping through our frequency counter of characters, and if the key is a divide it’s value by 2, then round it up to the nearest whole integer and replace a’s value.

This is the part that tripped me up the most.

THE EDGE CASES

The only thing we know is that the string is built by only using characters from the word instagram. Because of this, we are going to have to make a few assumptions due to how the problem is presented to us:

1.) The given string is empty (‘ ’ or ‘’)

Since we are dealing with characters in a string, we only have to take ‘ ’ or ‘’ into account and not worry about falsey statements like undefined, or null. We can tackle this with a single if statement if need be, but with the way we are thinking about our frequency counter object, a blank string will yield an empty object, and our running count will remain at 0.

2.) The given string has lower and uppercase letters, or consists of only uppercase letters

We can convert any string given to us into lowercase letters with .toLowerCase() before building our frequency counter of characters.

3.) The given string consists of multiple words and contains blank characters or spaces

We can write another if statement in the loop that builds our character count object that excludes spaces.

We don’t have to worry about numbers or special characters (!, ?, =, +, /, &, @, etc…) since we were told that the string we want to create only consists of letters in the word instagram, which is nice.

THE PSUEDO CODE

Now that we have broken down the problem and understand it, figured out a potential solution and explored some edge cases, let’s write out some pseudo code based off of what we have figured out so far:

I think our pseudo code looks pretty good, so let’s put that into practice and see if it works.

THE COMMENTS

First let’s define our function, our variables:

Simple enough. No real need for extra comments.

Next, we can write our for in loop that builds our frequency counter:

Then, we can write our for in loop that iterates through our frequency counter, normalizes it’s values, and sets our minimumStickers variable. We can also add our return statement, the variable minimumStickers:

If we test our solution with the three test cases provided, as well as some edge cases, we should get the results we are looking for:

Fantastic.

THE FINAL SOLUTION

Let’s take a final look at our solution without the comments, and clean up some of our syntax:

MISSION COMPLETE

The way I am going to write these blogs is going to follow a step by step formula. The most important thing I did once I started grinding through LeetCode was change my approach to solving each problem.

I used to immediately dive into writing code, console.log() everything I could and try to brute force a solution.

Eventually I realized how inefficient this was and slowly began adding steps to my approach before I write any code.

Now a days, I spend just as much time making sure I understand the problem I am presented with, figuring out edge cases and writing pseudo code as I do writing actual code and seeing if it works.

That was a massive step forward for me and the more I put this methodology into practice, the more I felt myself improving in my problem solving abilities.

I definitely understand my solutions won’t be the best or most efficient. The focus of this and future blogs is more about problem solving dynamics and how to break down a problem into smaller steps to figure out the code we could write, rather than finding the solution with the lowest time and space complexity.

I hope it helps you or someone else figure out a way to solve a problem they are stuck on…in this long and eloquent journey we call JavaScript.

Stay safe. Stay healthy. And keep fighting the good fight.

Coding Interview Questions | Skilled.dev