Find Words That Can Be Formed by Characters

• Initialize sum = 0.
• For each word in words:
  • Create a List<Character> from the chars string.
  • Initialize a boolean canForm = true.
  • For each character c in word:
    • If c is present in the list, remove one occurrence of c.
    • Else, set canForm = false and break the inner loop.
  • If canForm is true, add word.length() to sum.
• Return sum.

The algorithm starts by initializing a sum variable to zero. It then enters a loop that processes each word from the input words array. Inside this loop, a mutable copy of the chars string is created, typically as a List<Character>. This is necessary because we need to "use up" characters for each word independently. A boolean flag, say isGood, is set to true. A nested loop iterates through each character of the current word. In this inner loop, we check if the character exists in our list copy of chars. If it exists, we remove one instance of that character from the list to simulate its usage. If it does not exist, the word cannot be formed. We set isGood to false and immediately break out of the inner loop, as there's no need to check further for this word. After the inner loop finishes, we check the isGood flag. If it's still true, it means all characters of the word were found in chars, so we add the length of the word to our running sum. Finally, after checking all words, the total sum is returned.

1import java.util.ArrayList;2import java.util.List;3 4public class Solution {5    public int countCharacters(String[] words, String chars) {6        int goodWordsLengthSum = 0;7        for (String word : words) {8            List<Character> charList = new ArrayList<>();9            for (char c : chars.toCharArray()) {10                charList.add(c);11            }12            13            boolean isGood = true;14            for (char wordChar : word.toCharArray()) {15                // In Java, list.remove(Object) is needed to remove the element, not by index.16                if (charList.remove(Character.valueOf(wordChar))) {17                    // Character was found and removed.18                } else {19                    // Character was not found.20                    isGood = false;21                    break;22                }23            }24            25            if (isGood) {26                goodWordsLengthSum += word.length();27            }28        }29        return goodWordsLengthSum;30    }31}

• Create an integer array charsFreq of size 26, initialized to zeros.
• Iterate through each character c in chars and increment charsFreq[c - 'a'].
• Initialize sum = 0.
• For each word in words:
  • Create a temporary integer array wordFreq of size 26.
  • Iterate through each character c in word and increment wordFreq[c - 'a'].
  • Initialize a boolean canForm = true.
  • Iterate from i = 0 to 25. If wordFreq[i] > charsFreq[i], set canForm = false and break.
  • If canForm is true, add word.length() to sum.
• Return sum.

The core idea is to move from character-by-character searching to a frequency-based comparison. Since the input consists of only lowercase English letters, an integer array of size 26 is a perfect and efficient tool for a frequency map.

First, we create an integer array, charsFreq, of size 26. We iterate through the chars string once and populate this array. For each character c, we increment the count at index c - 'a'. This gives us a complete count of available characters in O(C) time, where C is the length of chars.

Next, we initialize a totalLength sum to 0 and iterate through each word in the words array. For each word, we build its own frequency map, wordFreq, in the same way. After building the wordFreq map, we compare it against the charsFreq map. We loop from 0 to 25 (representing 'a' to 'z') and check if wordFreq[i] is greater than charsFreq[i] for any i. If it is, the word requires more of a certain character than available, so it's not a "good" word. If we complete the comparison loop without finding such a case, the word is "good", and we add its length to our totalLength sum. This process avoids any expensive string or list operations within the main loop, making it very fast.

1public class Solution {2    public int countCharacters(String[] words, String chars) {3        int[] charsFreq = new int[26];4        for (char c : chars.toCharArray()) {5            charsFreq[c - 'a']++;6        }7        8        int goodWordsLengthSum = 0;9        for (String word : words) {10            int[] wordFreq = new int[26];11            for (char c : word.toCharArray()) {12                wordFreq[c - 'a']++;13            }14            15            boolean isGood = true;16            for (int i = 0; i < 26; i++) {17                if (wordFreq[i] > charsFreq[i]) {18                    isGood = false;19                    break;20                }21            }22            23            if (isGood) {24                goodWordsLengthSum += word.length();25            }26        }27        28        return goodWordsLengthSum;29    }30}