
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]
andchars
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:
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.
- Build a frequency map (such as a dictionary or list) for the characters in
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.
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
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 vectorcharCounts
of size 26 (representing the English alphabet) with all values set to zero and populates it by incrementing the count for each character in theavailableChars
.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 vectorcurrentWordCounts
.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 inavailableChars
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 tototalLength
.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 inavailableChars
.
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.
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 thechars
string. - Convert the
chars
string into a character array and update thecharCount
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 tocharCount
to tally the characters in the word. - Compare the
currentWordCount
of the word with thecharCount
. If the count of any character incurrentWordCount
exceeds that incharCount
, setisFormable
to false and break out of the loop. - If the word is formable (
isFormable
is true), add the word's length tototalLength
. - 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.
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 stringavailableChars
. - It then iterates through each character in
availableChars
, calculating the frequency of each character and updating thecharFrequency
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 listwordFreq
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 withavailableChars
. The check is performed by ensuring for every character, the frequency inavailableChars
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.
No comments yet.