Geek Culture
Published in

Geek Culture

Max Number of Words you Can Type: Using the Includes method

A walkthrough on how to solve this fun algorithm question using the includes method

Some of these algorithm questions can be quite interesting.

This one is no different — imagine having to use a computer with a broken keyboard. That would be quite the inconvenience, wouldn’t it?

Well, that’s the exact problem that we’re presented with here. In this fun (but frustrating world), we have to work with a broken keyboard and determine which words we can or cannot type.

Such a useful keyboard

Honestly speaking, my answer to this question would be to just throw out the keyboard and go buy a new one :)

But unfortunately, that was not an acceptable answer. So here we are, presented with this predicament. The problem states as follows:

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Note: This question is on Leetcode, question # 1935. Link to the question: https://leetcode.com/problems/maximum-number-of-words-you-can-type/

Let’s first plan out how we would approach this problem before we get into the code. Let’s get started!

The Approach

As with many problems, there are a few ways we can approach this. As a newer developer, what makes most sense to me is that we loop over both our input strings (text & brokenLetters) to check if we have any overlap. Therefore, we would need to use a nested loop.

  1. Convert text into an array of strings (separated by the space). Set it to a variable.
  2. Initialize a variable called result (we’ll return this at the end of our function). Set it to 0.
  3. Loop over the text input string
  4. Initialize a count variable inside the outer loop. Set it to 0. This will help us determine whether we need to increase our result count.
  5. Set inner loop and loop over brokenLetters input string
  6. Check if the text input includes letters from the brokenLetters input. If yes, increase count by 1.
  7. Check after each iteration if count is equal to 0 (which means text does not include any broken letters). If it is, increase result by 1

The Solution

Now that we have the roadmap laid out, let’s get to the code.

First, we’ll need to convert our text input into an array of strings separated by the space. We can use the .split method to achieve this.

We’ll also initialize our result variable here as well:

Next, we loop. First, we’ll loop over our text input string and then initialize a count variable and set it to 0. Again, we will use this to check whether we need to increase our result count. We then set an inner loop to loop over the brokenLetters input:

Next, we’ll use the .includes method to check whether each iteration (or string) of text includes the letter that we’re currently iterating over in brokenLetters. If there is a match, we would increase count by 1 -> therefore saying that we would be unable to type out the full word because the word would contain a letter that is broken.

On the contrary, if we see that count is 0, or that we are able to type out the full word because the word does not contain a letter that is broken, we would increase result by 1.

Return result at the end of our function will give us our final answer:

Conclusion

And there you have it! We’re able to solve this problem in quadratic time in a clear step-by-step approach.

I would love to hear your thoughts! If you have a more efficient approach or thoughts on my current approach, I would love to hear from you in the comment section below.

Until next time!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Warren Niu

Warren Niu

Uncovering the truths of Software Engineering one story at a time. Former Healthcare Administrator and proud dad of my Pomeranian, Nami. Based in Brooklyn, NY