CC-18 : Filter Strings by given filter criteria

Description:

Given an array of Strings named words, filter all words that match all filter criteria substrings found in 2nd input array subsets and return the filtered Strings.

Test cases and expected outputs:

Input Parameters	Expected outputs
words={"tree","free","be","red","he"}; subsets={"r","e"};	Matching words : tree,free,red
words={"radical","practical","logical"}; subsets={"cal"};	Matching words: radical,practical,logical
words={"radical","practical","logical"}; subsets={"calls"};	No matching words.

Pseudocode:

The java method should accept following input parameters: words (String array), subsets (String array).

Initialize a variable tempFreqMap of type HashMap to temporarily hold characters from input arrays as keys, and the frequency of these characters as the values.

Initialize a variable substFreqMap of type HashMap to hold characters from subsets as keys, and the frequency of these characters as the values.

Iterate through subsets:

For each character in the Strings in subsets, find the maximum frequency of that char across subsets’s strings. Store the char and the max frequency found in substFreqMap.

Initialize ArraysList of Strings named mtchWrdsAl to store word that match subsets.

Initialize a variable wordsFreqMap of type HashMap to hold characters from words as keys, and the frequency of these characters as the values.

Iterate through words :

For each character in the Strings in words, find the maximum frequency of that char across words ‘s Strings. Store the char and the max frequency found wordsFreqMap.

Iterate through keys of substFreqMap:

If frequency of characters part of substFreqMap is greater than frequency of same characters in wordsFreqMap, then the current word is a match and can be filtered. Add current word to mtchWrdsAl.

After above loop completes, mtchWrdsAl contains filtered words that match subsets array. Return mtchWrdsAl.toArray();

Code:

public String[] hashMapWordsSubset(String[] words, String[] subsets) throws Exception{
	HashMap< Character,Integer> tempFreqMap=new HashMap< Character, Integer>();
	HashMap< Character,Integer> sbstChrsFreqMap=new HashMap< Character, Integer>();
	String subset; char[] chars; int maxFreq;
	for (int sIdx=0; sIdx < subsets.length; sIdx++) {
		subset=subsets[sIdx];
		chars=subset.toCharArray();
		tempFreqMap.clear();
		for (int cIdx=0; cIdx < chars.length; cIdx++) {
			tempFreqMap.put(chars[cIdx], tempFreqMap.getOrDefault(chars[cIdx],0)+1);
			maxFreq=Math.max(tempFreqMap.getOrDefault(chars[cIdx],0), sbstChrsFreqMap.getOrDefault(chars[cIdx],0));
			sbstChrsFreqMap.put(chars[cIdx], maxFreq);
			
		}		
	}
	ArrayList< String> mtchWrdsAl=new ArrayList< String>();
	String word;
	HashMap< Character,Integer> wrdsFreqMap=new HashMap< Character, Integer>();
	for (int wIdx=0; wIdx < words.length; wIdx++) {
		word=words[wIdx];
		chars=word.toCharArray();
		wrdsFreqMap.clear();
		boolean notSubset=false;char substrchr;
		for (int cIdx=0; cIdx < chars.length; cIdx++) {
			wrdsFreqMap.put(chars[cIdx], wrdsFreqMap.getOrDefault(chars[cIdx],0)+1);			
		}
		notSubset=false; 
		Iterator itr=sbstChrsFreqMap.keySet().iterator();
		while (itr.hasNext()) {
			substrchr=(Character)itr.next();
			if ( (sbstChrsFreqMap.get(substrchr) > wrdsFreqMap.getOrDefault(substrchr, 0))) {
				notSubset=true;
				break;
			}
		}
		if (notSubset==false) {		
			mtchWrdsAl.add(word);
		}
	}
	String[] mtchWrdsArr=new String[mtchWrdsAl.size()];
	mtchWrdsAl.toArray(mtchWrdsArr);	
	return 	mtchWrdsArr;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;


public class HashMapWordsSubset {
	
public String[] hashMapWordsSubset(String[] words, String[] subsets) throws Exception{
	HashMap< Character,Integer> tempFreqMap=new HashMap< Character, Integer>();
	HashMap< Character,Integer> sbstChrsFreqMap=new HashMap< Character, Integer>();
	String subset; char[] chars; int maxFreq;
	for (int sIdx=0; sIdx < subsets.length; sIdx++) {
		subset=subsets[sIdx];
		chars=subset.toCharArray();
		tempFreqMap.clear();
		for (int cIdx=0; cIdx < chars.length; cIdx++) {
			tempFreqMap.put(chars[cIdx], tempFreqMap.getOrDefault(chars[cIdx],0)+1);
			maxFreq=Math.max(tempFreqMap.getOrDefault(chars[cIdx],0), sbstChrsFreqMap.getOrDefault(chars[cIdx],0));
			sbstChrsFreqMap.put(chars[cIdx], maxFreq);
			
		}		
	}
	ArrayList< String> mtchWrdsAl=new ArrayList< String>();
	String word;
	HashMap< Character,Integer> wrdsFreqMap=new HashMap< Character, Integer>();
	for (int wIdx=0; wIdx < words.length; wIdx++) {
		word=words[wIdx];
		chars=word.toCharArray();
		wrdsFreqMap.clear();
		boolean notSubset=false;char substrchr;
		for (int cIdx=0; cIdx < chars.length; cIdx++) {
			wrdsFreqMap.put(chars[cIdx], wrdsFreqMap.getOrDefault(chars[cIdx],0)+1);			
		}
		notSubset=false; 
		Iterator itr=sbstChrsFreqMap.keySet().iterator();
		while (itr.hasNext()) {
			substrchr=(Character)itr.next();
			if ( (sbstChrsFreqMap.get(substrchr) > wrdsFreqMap.getOrDefault(substrchr, 0))) {
				notSubset=true;
				break;
			}
		}
		if (notSubset==false) {		
			mtchWrdsAl.add(word);
		}
	}
	String[] mtchWrdsArr=new String[mtchWrdsAl.size()];
	mtchWrdsAl.toArray(mtchWrdsArr);	
	return 	mtchWrdsArr;
}
	
	
    
public static void main(String[] args) {
		
	HashMapWordsSubset hp=new HashMapWordsSubset();
	String[] retVal;
	try {
	String[] words={"tree","free","be","red","he"};
	String[] subsets={"r","e"};
	printArraySummary(words, "Words list");
	printArraySummary(subsets, "Subsets list");
	retVal=hp.hashMapWordsSubset(words, subsets);
	printArraySummary(retVal, "Matching list");
			
	String[] words1={"tree","free","be","red","he"};
	String[] subsets1={"te","r"};
	printArraySummary(words1, "Words list");
	printArraySummary(subsets1, "Subsets list");
	retVal=hp.hashMapWordsSubset(words1, subsets1);
	printArraySummary(retVal, "Matching list");
			
	String[] words2={"radical","practical","logical"};
	String[] subsets2={"cal"};
	printArraySummary(words2, "Words list");
	printArraySummary(subsets2, "Subsets list");
	retVal=hp.hashMapWordsSubset(words2, subsets2);
	printArraySummary(retVal, "Matching list");
			
	String[] words3={"radical","practical","logical"};
	String[] subsets3={"calls"};
	printArraySummary(words3, "Words list");
	printArraySummary(subsets3, "Subsets list");
	retVal=hp.hashMapWordsSubset(words3, subsets3);
	printArraySummary(retVal, "Matching list");
			
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
				
}

public static void printArraySummary(String[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex< intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("*************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

}