Find Words That Can Be Formed by Characters

Updated on 29 May, 2025
Find Words That Can Be Formed by Characters header image

Problem Statement

In this task, you are provided with an array of strings named words and a single string chars. A string from the words array is designated as good if you can entirely construct it using the characters from the chars string. Importantly, each character from chars can only be used once per word formation.

The ultimate goal is to calculate the total length of all the good strings that can be formed from the words array using the characters in chars. The result should represent the sum of the lengths of these good strings.

Examples

Example 1

Input:

words = ["cat","bt","hat","tree"], chars = "atach"

Output:

6

Explanation:

The strings that can be formed are "cat" and "hat".
The answer is 3 + 3 = 6.

Example 2

Input:

words = ["hello","world","tone"], chars = "welldonehoneyr"

Output:

10

Explanation:

The strings that can be formed are "hello" and "world".
The answer is 5 + 5 = 10.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length, chars.length <= 100
  • words[i] and chars consist of lowercase English letters.

Approach and Intuition

The problem reduces to checking whether each word in words can be formed from the characters in chars, considering character usage limits.

Steps:

  1. Count Characters in chars:

    • Build a frequency map (such as a dictionary or list) for the characters in chars to determine how many times each character can be used.
  2. Check Each Word:

    • For every word in words, create a frequency map for its characters.

    • Compare this with the chars frequency map:

      • If the word requires more of any character than is available, it is not valid.
      • Otherwise, the word is good, and its length contributes to the total.
  3. Return the Sum:

    • After checking all words, return the total length of the good words.

This method is efficient and well-suited for the problem's constraints, offering a linear scan over a limited alphabet (lowercase letters), making it scalable and straightforward.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    int calculateLength(vector<string>& wordList, string availableChars) {
        vector<int> charCounts(26, 0);
        for (char charItem : availableChars) {
            charCounts[charItem - 'a']++;
        }
        
        int totalLength = 0;
        for (string currentWord : wordList) {
            vector<int> currentWordCounts(26, 0);
            for (char character : currentWord) {
                currentWordCounts[character - 'a']++;
            }
            
            bool canFormWord = true;
            for (int i = 0; i < 26; i++) {
                if (charCounts[i] < currentWordCounts[i]) {
                    canFormWord = false;
                    break;
                }
            }
            
            if (canFormWord) {
                totalLength += currentWord.length();
            }
        }
        
        return totalLength;
    }
};

The provided C++ solution introduces a class named Solution that contains a single public method, calculateLength. This function calculates the sum of lengths of certain words from a list that can be entirely constructed using characters from a specified string.

Here’s a concise breakdown of how the implementation operates:

  • First, the solution utilizes a frequency count approach to determine how many times each character appears in the string availableChars. It initializes a vector charCounts of size 26 (representing the English alphabet) with all values set to zero and populates it by incrementing the count for each character in the availableChars.

  • Next, for each word in the provided wordList, the solution calculates the frequency of each character in that word using a similar approach and stores this data in a vector currentWordCounts.

  • For each word in the list, the solution checks, using a comparison loop, if availableChars contains enough characters to form the word. This is determined by ensuring the count of each character in availableChars is greater than or equal to that in the word.

  • If the conditions are met — meaning the word can indeed be formed from availableChars — the function accumulates the length of that word to totalLength.

  • Finally, after iterating through all words in the list, the function returns totalLength, which represents the sum of lengths of words that can be constructed from the characters provided in availableChars.

Key aspects to keep in mind include understanding the index mapping of characters to array indexes ('a' to 'z' mapped to 0 to 25) and the significance of ensuring the availability of required characters before considering a word's length.

java
class Solution {
    public int calculateLength(String[] words, String chars) {
        int[] charCount = new int[26];
        for (char character : chars.toCharArray()) {
            charCount[character - 'a']++;
        }

        int totalLength = 0;
        for (String word : words) {
            int[] currentWordCount = new int[26];
            for (char character : word.toCharArray()) {
                currentWordCount[character - 'a']++;
            }

            boolean isFormable = true;
            for (int i = 0; i < 26; i++) {
                if (charCount[i] < currentWordCount[i]) {
                    isFormable = false;
                    break;
                }
            }

            if (isFormable) {
                totalLength += word.length();
            }
        }

        return totalLength;
    }
}

This Java solution tackles the problem of finding the total length of words that can be formed using the given characters. The method calculateLength accepts an array of words and a string of characters, returning the total length of all words that can be fully formed.

  • Begin by initializing an array charCount to keep track of the frequency of each character in the chars string.
  • Convert the chars string into a character array and update the charCount array accordingly.
  • Initialize totalLength to zero, which will hold the cumulative length of all formable words.
  • Iterate over each word in the provided array of words. For each word, create a count array currentWordCount similar to charCount to tally the characters in the word.
  • Compare the currentWordCount of the word with the charCount. If the count of any character in currentWordCount exceeds that in charCount, set isFormable to false and break out of the loop.
  • If the word is formable (isFormable is true), add the word's length to totalLength.
  • Return the value of totalLength which represents the total length of all words that can be formed with the given characters.

This method efficiently calculates the total length by ensuring each word can be constructed with the available characters from the chars string, using simple character counting.

python
class Solution:
    def sumLengthOfWords(self, listOfWords: List[str], availableChars: str) -> int:
        charFrequency = [0] * 26
        for char in availableChars:
            charFrequency[ord(char) - ord('a')] += 1
        
        totalLength = 0
        for word in listOfWords:
            wordFreq = [0] * 26
            for char in word:
                wordFreq[ord(char) - ord('a')] += 1
            
            canFormWord = True
            for k in range(26):
                if charFrequency[k] < wordFreq[k]:
                    canFormWord = False
                    break
            
            if canFormWord:
                totalLength += len(word)
        
        return totalLength

The provided Python function sumLengthOfWords calculates the total length of all words from a list that can be formed using the characters from a given string. The solution involves counting the frequency of each character in the given string and in each word, and then checking if the word can be completely formed by the characters in the given string.

Here's a breakdown of the function:

  • First, it initializes an array charFrequency with 26 zeros, representing the frequency of each character from 'a' to 'z' in the string availableChars.
  • It then iterates through each character in availableChars, calculating the frequency of each character and updating the charFrequency list accordingly.
  • The variable totalLength is initialized to zero, which will hold the sum of the lengths of all words that can be formed.
  • For each word in listOfWords, a new frequency list wordFreq is created to store the frequency of each letter in the word.
  • After populating the wordFreq list, it checks character by character to ensure that the word can be formed with availableChars. The check is performed by ensuring for every character, the frequency in availableChars is not less than the frequency in the word.
  • If the word can be formed, its length is added to totalLength.
  • Finally, the function returns the totalLength.

This function effectively allows to determine how many and which words from the list can be constructed using only the characters available in the specified string, summing up their lengths as the output.

Comments

No comments yet.