Find Words That Can Be Formed by Characters
Sum lengths of words whose characters are a multiset subset of an inventory string.
4 min read
hash-map counting strings
Problem#
Given words and a string chars, return the sum of lengths of words that can be formed using letters from chars (each chars letter used at most once per word).
Examples#
words = ["cat","bt","hat","tree"], chars = "atach"→6("cat"+"hat").words = ["hello","world","leetcode"], chars = "welldonehoneyr"→10("hello"+"world").
Constraints#
1 <= words.length <= 1000,1 <= words[i].length, chars.length <= 100.
Hints#
Hint
Count
chars once; for each word check cnt[word][c] <= cnt[chars][c] per letter. Approach#
Count chars letters. For each word, count its letters; if every letter’s count fits in chars, add word’s length.
Solution#
class Solution {public: int countCharacters(vector<string>& words, string chars) { int avail[26] = {0}; for (char c : chars) ++avail[c - 'a']; int ans = 0; for (auto& w : words) { int need[26] = {0}; for (char c : w) ++need[c - 'a']; bool ok = true; for (int i = 0; i < 26; ++i) if (need[i] > avail[i]) { ok = false; break; } if (ok) ans += w.size(); } return ans; }};func countCharacters(words []string, chars string) int { var avail [26]int for i := 0; i < len(chars); i++ { avail[chars[i]-'a']++ } ans := 0 for _, w := range words { var need [26]int for i := 0; i < len(w); i++ { need[w[i]-'a']++ } ok := true for i := 0; i < 26; i++ { if need[i] > avail[i] { ok = false break } } if ok { ans += len(w) } } return ans}from collections import Counterfrom typing import List
class Solution: def countCharacters(self, words: List[str], chars: str) -> int: avail = Counter(chars) ans = 0 for w in words: need = Counter(w) if all(need[c] <= avail[c] for c in need): ans += len(w) return ansvar countCharacters = function(words, chars) { const avail = new Array(26).fill(0); const A = 'a'.charCodeAt(0); for (let i = 0; i < chars.length; i++) avail[chars.charCodeAt(i) - A]++; let ans = 0; for (const w of words) { const need = new Array(26).fill(0); for (let i = 0; i < w.length; i++) need[w.charCodeAt(i) - A]++; let ok = true; for (let i = 0; i < 26; i++) { if (need[i] > avail[i]) { ok = false; break; } } if (ok) ans += w.length; } return ans;};class Solution { public int countCharacters(String[] words, String chars) { int[] avail = new int[26]; for (int i = 0; i < chars.length(); i++) avail[chars.charAt(i) - 'a']++; int ans = 0; for (String w : words) { int[] need = new int[26]; for (int i = 0; i < w.length(); i++) need[w.charAt(i) - 'a']++; boolean ok = true; for (int i = 0; i < 26; i++) { if (need[i] > avail[i]) { ok = false; break; } } if (ok) ans += w.length(); } return ans; }}function countCharacters(words: string[], chars: string): number { const avail: number[] = new Array(26).fill(0); const A = 'a'.charCodeAt(0); for (let i = 0; i < chars.length; i++) avail[chars.charCodeAt(i) - A]++; let ans = 0; for (const w of words) { const need: number[] = new Array(26).fill(0); for (let i = 0; i < w.length; i++) need[w.charCodeAt(i) - A]++; let ok = true; for (let i = 0; i < 26; i++) { if (need[i] > avail[i]) { ok = false; break; } } if (ok) ans += w.length; } return ans;}Editorial#
Per-word per-letter comparison is the cleanest read. We use disposable need[] arrays per word so chars isn’t mutated — necessary since each word is checked independently.
Complexity#
- Time: O(sum of word lengths + words * 26).
- Space: O(1).
Concept revision#
Related#