Code Destine

Problem Statement

You have given an array of words and a string S. A word is good if it can be formed by using characters from string S (each character can only be used once).

Write a program to find out the sum of the length of all good words in the given array.

Example 

Input :- Words = ["cat","bt","hat","tree"], S = "atach"
Output :- 6

Input :- Words = ["hello","world","morning"], S = "welldonehoneyr"
Output :- 10

Solution

To solve this problem, we have to compare the frequency of each character in the word with the frequency of that character in the string S.

This problem can be solved in following steps :-

1. Create the character array from the input String S.
2. Create an integer array (count array) of size 26 (Total number of characters in the English language), This array will be used to store the frequency of each character in the S string.
3. Traverse the S character array from start (index 0) to end (n-1, where n is the length of an array) and convert each character into an index of count array by subtracting the character from ‘a’ and converting it into ASCII code. Increase the count for the calculated index by 1.
4. Traverse the array of words and for each word, repeat steps 1, 2 and 3. If the frequency of any character in the word is greater than the frequency of that character in S string, then that word is not a good word.
5. Add and return the length of all good words.

Program

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		int result = main.countCharacters(new String[] {"hello","world","morning"}, "welldonehoneyr");
		System.out.println(result);
	}
	
	/* Solution */    
	public int countCharacters(String[] words, String chars) {
        
        int[] countArray = new int[26];
        for(char c : chars.toCharArray()){            
            countArray[c-'a']++;
        }
        
        int sum = 0;
        int[] array = new int[26];
        char[] ch = null;
        boolean isGood = false;
        for(String word : words){
            
            Arrays.fill(array, 0);
            ch = word.toCharArray();
            isGood = true;
            for(int i=0; i<ch.length; i++){            
                array[ch[i]-'a']++;
                if(countArray[ch[i]-'a'] - array[ch[i]-'a'] <0){
                    isGood = false;
                    break;
                }
            }
            
            if(isGood){
                sum = sum + word.length();
            }            
        }
        return sum;
    }
}

Result

10

Similar Post

1. Height Checker
2. Day of the Week
3. Move Zeroes to End of Array

That’s all for Find Words That Can Be Formed by Characters in Java, If you liked it, please share your thoughts in a comments section and share it with others too.