You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach" Output: 6 Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr" Output: 10 Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
Constraints:
1 <= words.length <= 10001 <= words[i].length, chars.length <= 100words[i] and chars consist of lowercase English letters.This approach involves counting the frequency of each character in the 'chars' string. For each word, check if the word can be constructed using these characters, respecting their frequencies.
This solution counts the frequency of each character in the 'chars' array using an integer array of size 26. For each word, it creates a frequency array to check if the word can be formed without exceeding the available characters and their counts.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'.
Space Complexity: O(1), as the auxiliary space used is constant, i.e., the two arrays of size 26.
This approach utilizes hash maps to count the frequency of characters in both the 'chars' string and each word. The map allows for dynamic sizing and flexibility with character counts.
This solution counts the frequencies of characters using hash maps for both 'chars' and each word. It checks if the words can be formed by comparing counts in these maps and adds the lengths of words that can be formed.
Python
Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'.
Space Complexity: O(1), additional space overhead is minimal with the unordered maps.
| Approach | Complexity |
|---|---|
| Character Frequency Counting | Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'. |
| Map-based Character Counting | Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'. |
LeetCode Find Words That Can Be Formed by Characters Solution Explained - Java • Nick White • 11,826 views views
Watch 9 more video solutions →Practice Find Words That Can Be Formed by Characters with our built-in code editor and test cases.
Practice on FleetCode