Find Words That Can Be Formed by Characters

Sum lengths of words whose characters are a multiset subset of an inventory string.

Easy
Time O(N) Space O(1)
LeetCode
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#

Find Words That Can Be Formed by Characters
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.