Find Words That Can Be Formed by Characters — Solution
Find Words That Can Be Formed by Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find Words That Can Be Formed by Characters is an easy coding problem on strings, hash table and counting, asked in Amazon, TCS and Infosys interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, TCS, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A word can be formed from chars if every letter it uses is available in chars at least as many times. Each letter of chars may be used at most once per word, but chars is not consumed between words.
Return the sum of the lengths of all words that can be formed.
Example 1
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: "cat" and "hat" can be formed: 3 + 3 = 6.
Example 2
Input: words = ["code","kairo","coco"], chars = "codekairo"
Output: 9
Explanation: "code" and "kairo" fit; "coco" needs two c's and only one is available.
Example 3
Input: words = ["a"], chars = "b"
Output: 0
Constraints
1 <= words.length <= 10001 <= words[i].length, chars.length <= 100All strings consist of lowercase English letters.
Hints for Find Words That Can Be Formed by Characters
Hint 1
Count the letters of
charsonce — the budget is the same for every word.Hint 2
For each word, count its own letters and compare slot by slot.
Hint 3
Counts, not membership:
"cook"needs twoos.
How to solve Find Words That Can Be Formed by Characters
The budget is fixed, so tally chars once and then test each word against it with a 26-slot comparison.
Approach
- Build
have[26]fromchars. - For each word, build
need[26]and checkneed[c] <= have[c]for every letter. - Add the word's length when every slot passes.
Why it works
Because chars is not consumed between words, each word is an independent test against the same budget — so recomputing have per word would be wasted work, and a shared mutable budget would be wrong.
Complexity
- Time —
O(total characters) - Space —
O(1)
Pitfalls
- Decrementing
haveas words are matched treatscharsas consumable, which the statement does not. - A set-based check ignores multiplicity and accepts
"cook"from"cok".
Reference solution
Python
from typing import List
def countCharacters(words: List[str], chars: str) -> int:
have = [0] * 26
for c in chars:
have[ord(c) - 97] += 1
total = 0
for w in words:
need = [0] * 26
for c in w:
need[ord(c) - 97] += 1
if all(need[i] <= have[i] for i in range(26)):
total += len(w)
return totalJava
public static int countCharacters(String[] words, String chars) {
int[] have = new int[26];
for (int i = 0; i < chars.length(); i++) have[chars.charAt(i) - 'a']++;
int total = 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 c = 0; c < 26; c++) {
if (need[c] > have[c]) { ok = false; break; }
}
if (ok) total += w.length();
}
return total;
}C++
int countCharacters(vector<string>& words, string chars) {
vector<int> have(26, 0);
for (char c : chars) have[c - 'a']++;
int total = 0;
for (const string& w : words) {
vector<int> need(26, 0);
for (char c : w) need[c - 'a']++;
bool ok = true;
for (int c = 0; c < 26; c++) {
if (need[c] > have[c]) { ok = false; break; }
}
if (ok) total += (int) w.size();
}
return total;
}JavaScript
var countCharacters = function(words, chars) {
var have = [];
for (var t = 0; t < 26; t++) have.push(0);
for (var i = 0; i < chars.length; i++) have[chars.charCodeAt(i) - 97]++;
var total = 0;
for (var j = 0; j < words.length; j++) {
var w = words[j];
var need = [];
for (var u = 0; u < 26; u++) need.push(0);
for (var k = 0; k < w.length; k++) need[w.charCodeAt(k) - 97]++;
var ok = true;
for (var c = 0; c < 26; c++) {
if (need[c] > have[c]) { ok = false; break; }
}
if (ok) total += w.length;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets