Longest Words Containing Given Characters

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

/*
 * @Author: Ajk Palikuqi
 * 
 * @Question: How to Find the Longest Words Containing Given Characters in a List
 * 
 */

package iqLib.stringLib;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class LongestWordFromLetters
{
   private static double MAX_ALLOWED_FILESIZE_IN_MEMORY = 10*1024*1024; //10 MB

   public static void main(String[] args) throws FileNotFoundException, IOException
   {
      if (args.length &lt; 1)
      {
         System.out.println("You need at least 1 argument to run this script!");
         return;
      }
      
      String filename = args[0];
      int charArgIndex = 1;
      Map&lt;Character, Integer> possibleChars = new HashMap&lt;Character, Integer>();
      
      while (args.length > charArgIndex)
      {
         if (args[charArgIndex].length() != 1)
         {
            System.out.println("All arguments following the filename need to be single characters!");
            return;
         }
         
         char currentChar = args[charArgIndex].charAt(0);
         int charOccurenceTimes = 1;
         
         if (possibleChars.containsKey(currentChar))
         {
            charOccurenceTimes = possibleChars.get(currentChar) + 1;
         }

         possibleChars.put(currentChar, charOccurenceTimes);
      }
      
      File wordsFile = new File(filename);
      double fileLengthInBytes = wordsFile.length();
      
      if (fileLengthInBytes &lt; MAX_ALLOWED_FILESIZE_IN_MEMORY)
      {
         printLongestWordsFromMemory(wordsFile, possibleChars);
      }
      else
      {
         int longestWordSize = findLongestWordSize(wordsFile);
         printWordsFromStream(wordsFile, longestWordSize, possibleChars);
      }
   }
      
   private static void printLongestWordsFromMemory(File wordsFile, 
      Map&lt;Character, Integer> possibleChars) throws FileNotFoundException, IOException
   {
      int longestWordLength = 0;
      ArrayList&lt;String> longestWords = new ArrayList&lt;String>();
      InputStreamReader sReader = new InputStreamReader(new FileInputStream(wordsFile));
      BufferedReader buffReader = new BufferedReader(sReader);
      String currentLine;

      while((currentLine = buffReader.readLine()) != null)
      {
         int lineLength = currentLine.length();

         if (lineLength >= longestWordLength)
         {
            if (lineLength > longestWordLength)
            {
               longestWords.clear();
               longestWordLength = lineLength;
            }

            longestWords.add(currentLine);
         }
      }

      for (String word : longestWords)
      {
         if(canWordBeConstructedFromChars(word, possibleChars))
         {
            System.out.println(word);
         }
      }
   }

   private static int findLongestWordSize(File wordsFile) throws FileNotFoundException, IOException
   {
      int longestWordLength = 0;
      InputStreamReader sReader = new InputStreamReader(new FileInputStream(wordsFile));
      BufferedReader buffReader = new BufferedReader(sReader);
      String currentLine;

      while((currentLine = buffReader.readLine()) != null)
      {
         int lineLength = currentLine.length();

         if (currentLine.length() > longestWordLength)
         {
            longestWordLength = lineLength;
         }
      }

      return longestWordLength;
   }

   private static void printWordsFromStream(File wordsFile, int wordsLength, 
      Map&lt;Character, Integer> possibleChars) throws FileNotFoundException, IOException
   {
      InputStreamReader sReader = new InputStreamReader(new FileInputStream(wordsFile));
      BufferedReader buffReader = new BufferedReader(sReader);
      String currentLine;
      
      while((currentLine = buffReader.readLine()) != null)
      {
         if (currentLine.length() == wordsLength)
         {
            if(canWordBeConstructedFromChars(currentLine, possibleChars))
            {
               System.out.println(currentLine);
            }
         }
      }
   }

   private static boolean canWordBeConstructedFromChars(String word, Map&lt;Character, Integer> possibleChars)
   {
      Map&lt;Character, Integer> charsInWord = new HashMap&lt;Character, Integer>();

      for (int i = word.length() - 1; i >= 0; --i)
      {
         char currentChar = word.charAt(0);
         int charOccurenceTimes = 1;

         if (charsInWord.containsKey(currentChar))
         {
            charOccurenceTimes = charsInWord.get(currentChar) + 1;
         }
         
         if (possibleChars.get(currentChar) > charOccurenceTimes)
         {
            return false;
         }

         charsInWord.put(currentChar, charOccurenceTimes);
      }

      return true;
   }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

* @Author: Ajk Palikuqi

* @Question: How to Find the Longest Words Containing Given Characters in a List

package iqLib.stringLib;

import java.io.BufferedReader;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Map;

public class LongestWordFromLetters

{

private static double MAX_ALLOWED_FILESIZE_IN_MEMORY = 10*1024*1024; //10 MB

public static void main(String[] args) throws FileNotFoundException, IOException

{

if (args.length < 1)

{

System.out.println("You need at least 1 argument to run this script!");

return;

}

String filename = args[0];

int charArgIndex = 1;

Map<Character, Integer> possibleChars = new HashMap<Character, Integer>();

while (args.length > charArgIndex)

{

if (args[charArgIndex].length() != 1)

{

System.out.println("All arguments following the filename need to be single characters!");

return;

}

char currentChar = args[charArgIndex].charAt(0);

int charOccurenceTimes = 1;

if (possibleChars.containsKey(currentChar))

{

charOccurenceTimes = possibleChars.get(currentChar) + 1;

}

possibleChars.put(currentChar, charOccurenceTimes);

}

File wordsFile = new File(filename);

double fileLengthInBytes = wordsFile.length();

if (fileLengthInBytes < MAX_ALLOWED_FILESIZE_IN_MEMORY)

{

printLongestWordsFromMemory(wordsFile, possibleChars);

}

else

{

int longestWordSize = findLongestWordSize(wordsFile);

printWordsFromStream(wordsFile, longestWordSize, possibleChars);

}

private static void printLongestWordsFromMemory(File wordsFile,

Map<Character, Integer> possibleChars) throws FileNotFoundException, IOException

{

int longestWordLength = 0;

ArrayList<String> longestWords = new ArrayList<String>();

InputStreamReader sReader = new InputStreamReader(new FileInputStream(wordsFile));

BufferedReader buffReader = new BufferedReader(sReader);

String currentLine;

while((currentLine = buffReader.readLine()) != null)

{

int lineLength = currentLine.length();

if (lineLength >= longestWordLength)

{

if (lineLength > longestWordLength)

{

longestWords.clear();

longestWordLength = lineLength;

}

longestWords.add(currentLine);

}

for (String word : longestWords)

{

if(canWordBeConstructedFromChars(word, possibleChars))

{

System.out.println(word);

}

private static int findLongestWordSize(File wordsFile) throws FileNotFoundException, IOException

{

int longestWordLength = 0;

InputStreamReader sReader = new InputStreamReader(new FileInputStream(wordsFile));

BufferedReader buffReader = new BufferedReader(sReader);

String currentLine;

while((currentLine = buffReader.readLine()) != null)

{

int lineLength = currentLine.length();

if (currentLine.length() > longestWordLength)

{

longestWordLength = lineLength;

}

return longestWordLength;

}

private static void printWordsFromStream(File wordsFile, int wordsLength,

Map<Character, Integer> possibleChars) throws FileNotFoundException, IOException

{

InputStreamReader sReader = new InputStreamReader(new FileInputStream(wordsFile));

BufferedReader buffReader = new BufferedReader(sReader);

String currentLine;

while((currentLine = buffReader.readLine()) != null)

{

if (currentLine.length() == wordsLength)

{

if(canWordBeConstructedFromChars(currentLine, possibleChars))

{

System.out.println(currentLine);

}

private static boolean canWordBeConstructedFromChars(String word, Map<Character, Integer> possibleChars)

{

Map<Character, Integer> charsInWord = new HashMap<Character, Integer>();

for (int i = word.length() - 1; i >= 0; --i)

{

char currentChar = word.charAt(0);

int charOccurenceTimes = 1;

if (charsInWord.containsKey(currentChar))

{

charOccurenceTimes = charsInWord.get(currentChar) + 1;

}

if (possibleChars.get(currentChar) > charOccurenceTimes)

{

return false;

}

charsInWord.put(currentChar, charOccurenceTimes);

}

return true;

}

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++