Learn-dsa..in 30 days!



























CC-3 : Check if String can be formed from given characters.

Description:

Given String str and array of characters chars, check how many times str can be formed by utilizing characters in chars.

Test cases and expected outputs:

Input Parameters Expected outputs
charsStr="aazzeeccc";
target="ace"; 		Target String can be made 2 times from character array
charsStr="ccnnssaar";
target="car"; 		Target String can be made 1 times from character array
charsStr="ttnnanqqqq";
target=" ten"; 		Target String cannot be made from character array
charsStr="ccggcaaaaclllleellqq";
target="call"; 		Target String can be made 3 times from character array

Pseudocode:

The java method should accept following input parameters: chars (character array) and str (String).
Initialize a variable chrFreqMap of type HashMap to hold the characters from chars and their frequencies.
Iterate through chars using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches chars.length-1:
If chrFreqMap does not contain key chars[idx], then put key-value pair chars[idx] and 0 to chrFreqMap.
If chrFreqMap contains key chars[idx] with value freq, then put key-value pair chars[idx] and freq+1 to chrFreqMap.
After completion of above loop, chrFreqMap contains keys that are characters of chars and values corresponding to each character key is the frequency of that character in chars.
Initialize a variable strFreqMap of type HashMap to hold the characters from str and their frequencies.
Iterate through str using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches str.length()-1:
If strFreqMap does not contain key str.charAt(idx), then put key-value pair str.CharAt(idx) and 0 to strFreqMap.
If strFreqMap contains key str.charAt(idx) with value freq, then put key-value pair str.charAt(idx) and freq+1 to strFreqMap.
After completion of above loop, strFreqMap contains keys that are characters of str and values corresponding to each character key is the frequency of that character in str.
Define integer variable minMult=Integer.Max;
Now, iterate through each key c of strFreqMap:
If chrFreqMap does not contain c, then str cannot be formed from chars, return 0 from the program.
Else divide frequency of c in chrFreqMap with frequency of c in strFreqMap and store it in int variable mult.
If mult < minMult:
Set minMult=mult.
At end of above iteration of all keys of strFreqMap, the variable minMult contains the maximum number of times str can be formed by utilizing chars from chars. Return minMult.

Code:

public int hashMapCheckCharsMakeStr(char[] chars, String str) throws Exception{
	HashMap< Character,Integer> chrFreqMap=new HashMap< Character, Integer>();
	for (int idx=0; idx < chars.length; idx++) {
		chrFreqMap.put(chars[idx], chrFreqMap.getOrDefault(chars[idx],0)+1);
	}
	HashMap< Character,Integer> strFreqMap=new HashMap<Character, Integer>();
	for (int idx=0; idx < str.length(); idx++) {
		strFreqMap.put(str.charAt(idx), strFreqMap.getOrDefault(str.charAt(idx),0)+1);
	}
	Iterator< Character> itr=strFreqMap.keySet().iterator();
	int minMult=Integer.MAX_VALUE;
	int mult=0;
	while (itr.hasNext()) {
		char c=itr.next();
		if (chrFreqMap.containsKey(c)==false) {return 0;}
		mult=chrFreqMap.getOrDefault(c,0) / strFreqMap.getOrDefault(c,0);
		if (mult < minMult ) {minMult=mult;}
	}		
	return minMult;		
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us