Press "Enter" to skip to content

How to Find the Longest Words Containing Given Characters in a List

Ajk 0

Today I wanted to discuss quickly a simple looking question regarding finding longest words containing given characters. This time we are not dealing with a very tech savvy guy, so he does not give us much clarifications other than a sample command line of how the software is supposed to work.

> wordList.txt d e w i a s z c x t g o b
date
dice
gas
iceboats
tax
box

He is very particular about the fact that the words should not contain the characters for more times than they appear in the input (i.e. ‘bass’ should not be returned from above since we only have one ‘s’.)

As we gathered all the requirement we set off to write our code. This is a pretty fun problem since we are going to do some File work and command line main method and you are probably going to be able to test it yourself ;).

How to Find the Longest Words Containing Given Characters in a List

I am not gonna lie, it took me about 30-40 mins to write the above code, but finally I am satisfied.
Things to note on the algorithm:

  • We are dealing with a file, whether it’s better to get all the file in memory or deal with I/O overhead depends on the filesize
  • The overall complexity of our algorithm is O(N) time and O(1) space for big files!! (with the #dicey assumption of Maps running at O(1))
  • Food for thought: We do not handle the exceptions. Should we? If so in the main method or the helper methods?
  • Food for thought: For long files, what about pre-computing pairs of chars that go together to aid our search?

Here is a similar question in C++

As always you can find this and other solutions on my GitHub page!
Hope you guys enjoyed it, and I’ll see you guys next time! ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂