Find Words That Can Be Formed by Characters solution and explanation
Google
9 more videos on this problem
Find Words That Can Be Formed by Characters | META | Leetcode 1160codestorywithMIK · 7:23 · 13K views
LeetCode Find Words That Can Be Formed by Characters Solution Explained - JavaNick White · 8:20 · 12K views
Find Words That Can Be Formed by Characters - Leetcode 1160 - PythonNeetCodeIO · 7:16 · 8K views
LeetCode 1160 : Find Words that can be formed by Characters [Solution]Ali Reza · 13:56 · 1K views
Leetcode 1160. Find Words That Can Be Formed by Characters PythonTechZoo · 4:00 · 994 views
1160. Find Words That Can Be Formed by Characters (Leetcode Easy)Programming Live with Larry · 6:00 · 898 views
Find Words That Can Be Formed by Characters - LeetCode #1160 - Python, JavaScript, Java and C++CodingNinja · 8:33 · 673 views
1160. Find Words That Can Be Formed By Characters Java SolutionCode with Carter · 12:37 · 614 views
Solving LeetCode 1160 Find Words That Can Be Formed by Characters | Hash Table | Google | AmazonCode Harmony · 11:03 · 550 views
How to Solve "1160 Find Words That Can Be Formed by Characters" on LeetCode - JavascriptBecoming A Better Dev (with David) · 10:49 · 423 views
The problem
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]andcharsconsist of lowercase English letters.
Approach overview
Problem Overview: You receive a list of words and a string chars. Each character in chars can be used only once. The task is to determine which words can be constructed using those characters and return the total length of all valid words.
Approach 1: Character Frequency Counting (O(W * K) time, O(1) space)
The most efficient method relies on fixed-size frequency counting. First compute a frequency array of size 26 for chars. Then iterate through each word and build another 26-length counter for that word. Compare the counts: if any character appears more times in the word than in chars, the word cannot be formed. If all counts fit within the available supply, add the word’s length to the result. Since the alphabet is limited to lowercase English letters, the counter size remains constant, giving O(1) auxiliary space. This approach is straightforward and performs well because comparisons are constant-time operations over a small array.
This technique commonly appears in problems involving counting and string manipulation. You iterate through characters once, update counters, and validate availability using direct index access.
Approach 2: Map-based Character Counting (O(W * K) time, O(K) space)
This variation uses a hash map to track frequencies instead of a fixed array. Build a frequency map for chars. For each word, construct another map while iterating through its characters. During the check phase, verify that each character’s frequency in the word does not exceed the frequency in the base map. If all checks pass, accumulate the word length.
The logic mirrors the array-counting approach but uses dynamic storage rather than fixed indexing. Time complexity remains O(W * K), where W is the number of words and K is the average word length. Space complexity becomes O(K) due to per-word maps. This approach is useful when working with larger character sets or when the problem is framed around hash table operations.
Recommended for interviews: Character Frequency Counting. Interviewers expect you to recognize that the alphabet size is fixed and replace hash maps with a small array. The map-based approach still demonstrates correct reasoning, but the array solution shows stronger awareness of constant-space optimizations and typical patterns used in array-based counting problems.
Approach 1: Character Frequency Counting
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.
def count_characters(words, chars):
from collections import Counter
char_count = Counter(chars)
total_length = 0
for word in words:
word_count = Counter(word)
for letter, cnt in word_count.items():
if cnt > char_count[letter]:
break
else:
total_length += len(word)
return total_length
words = ["cat", "bt", "hat", "tree"]
chars = "atach"
print(count_characters(words, chars)) # Output: 6import java.util.*;
public class Solution {
public int countCharacters(String[] words, String chars) {
int[] charCount = new int[26];
for (char ch : chars.toCharArray()) {
charCount[ch - 'a']++;
}
int result = 0;
for (String word : words) {
int[] wordCount = new int[26];
for (char ch : word.toCharArray()) {
wordCount[ch - 'a']++;
}
if (canFormWord(wordCount, charCount)) {
result += word.length();
}
}
return result;
}
private boolean canFormWord(int[] wordCount, int[] charCount) {
for (int i = 0; i < 26; i++) {
if (wordCount[i] > charCount[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Solution s = new Solution();
String[] words = {"cat", "bt", "hat", "tree"};
String chars = "atach";
System.out.println(s.countCharacters(words, chars)); // Output: 6
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int countCharacters(vector<string>& words, string chars) {
vector<int> charCount(26, 0);
for (char c : chars) {
charCount[c - 'a']++;
}
int result = 0;
for (string word : words) {
vector<int> wordCount(26, 0);
for (char c : word) {
wordCount[c - 'a']++;
}
bool canForm = true;
for (int i = 0; i < 26; i++) {
if (wordCount[i] > charCount[i]) {
canForm = false;
break;
}
}
if (canForm) {
result += word.length();
}
}
return result;
}
int main() {
vector<string> words = {"cat", "bt", "hat", "tree"};
string chars = "atach";
cout << countCharacters(words, chars) << endl; // Output: 6
return 0;
}function countCharacters(words, chars) {
let charCount = new Array(26).fill(0);
for (let c of chars) {
charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
let result = 0;
for (let word of words) {
let wordCount = new Array(26).fill(0);
for (let c of word) {
wordCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
let canForm = true;
for (let i = 0; i < 26; i++) {
if (wordCount[i] > charCount[i]) {
canForm = false;
break;
}
}
if (canForm) {
result += word.length;
}
}
return result;
}
const words = ["cat", "bt", "hat", "tree"];
const chars = "atach";
console.log(countCharacters(words, chars)); // Output: 6#include <stdio.h>
#include <string.h>
int countCharacters(char **words, int wordsSize, char *chars) {
int charCount[26] = {0};
for (int i = 0; chars[i] != '\0'; i++) {
charCount[chars[i] - 'a']++;
}
int result = 0;
for (int i = 0; i < wordsSize; i++) {
int wordCount[26] = {0};
for (int j = 0; words[i][j] != '\0'; j++) {
wordCount[words[i][j] - 'a']++;
}
int canForm = 1;
for (int k = 0; k < 26; k++) {
if (wordCount[k] > charCount[k]) {
canForm = 0;
break;
}
}
if (canForm) {
result += strlen(words[i]);
}
}
return result;
}
int main() {
char *words[] = {"cat", "bt", "hat", "tree"};
char chars[] = "atach";
int wordsSize = 4;
printf("%d\n", countCharacters(words, wordsSize, chars)); // Output: 6
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountCharacters(string[] words, string chars) {
int[] charCount = new int[26];
foreach (char c in chars) {
charCount[c - 'a']++;
}
int result = 0;
foreach (string word in words) {
int[] wordCount = new int[26];
foreach (char c in word) {
wordCount[c - 'a']++;
}
bool canForm = true;
for (int i = 0; i < 26; i++) {
if (wordCount[i] > charCount[i]) {
canForm = false;
break;
}
}
if (canForm) {
result += word.Length;
}
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = { "cat", "bt", "hat", "tree" };
string chars = "atach";
Console.WriteLine(sol.CountCharacters(words, chars)); // Output: 6
}
}The Python solution utilizes the Counter class from the collections module to track the frequency of characters. It loops through each word, checking if the word can be composed using the available character counts and adds up the length if possible.
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 beyond the input and output sizes, though Counter has its own overhead.
Approach 2: Map-based Character Counting
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.
def count_characters(words, chars):
from collections import Counter
char_count = Counter(chars)
total_length = 0
for word in words:
word_count = Counter(word)
if all(word_count[ch] <= char_count[ch] for ch in word_count):
total_length += len(word)
return total_length
words = ["cat", "bt", "hat", "tree"]
chars = "atach"
print(count_characters(words, chars)) # Output: 6#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
int countCharacters(vector<string>& words, string chars) {
unordered_map<char, int> charMap;
for (char c : chars) {
charMap[c]++;
}
int result = 0;
for (string word : words) {
unordered_map<char, int> wordMap;
for (char c : word) {
wordMap[c]++;
}
bool canForm = true;
for (auto& entry : wordMap) {
if (entry.second > charMap[entry.first]) {
canForm = false;
break;
}
}
if (canForm) {
result += word.length();
}
}
return result;
}
int main() {
vector<string> words = {"cat", "bt", "hat", "tree"};
string chars = "atach";
cout << countCharacters(words, chars) << endl; // Output: 6
return 0;
}Using Python's Counter for character mapping, this solution compares each word's character needs to that available in 'chars'. It uses a single line check with all() to determine if the word can be formed.
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), with the Counter managing internal structures efficiently.
Approach 3: Counting
We can use an array cnt of length 26 to count the occurrence of each letter in the string chars.
Then we traverse the string array words. For each string w, we use an array wc of length 26 to count the occurrence of each letter in the string w. If for each letter c, wc[c] leq cnt[c], then we can spell the string w with the letters in chars, otherwise we cannot spell the string w. If we can spell the string w, then we add the length of the string w to the answer.
After the traversal, we can get the answer.
The time complexity is O(L), and the space complexity is O(C). Here, L is the sum of the lengths of all strings in the problem, and C is the size of the character set. In this problem, C = 26.
function countCharacters(words: string[], chars: string): number {
const idx = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
const cnt = new Array(26).fill(0);
for (const c of chars) {
cnt[idx(c)]++;
}
let ans = 0;
for (const w of words) {
const wc = new Array(26).fill(0);
let ok = true;
for (const c of w) {
if (++wc[idx(c)] > cnt[idx(c)]) {
ok = false;
break;
}
}
if (ok) {
ans += w.length;
}
}
return ans;
}func countCharacters(words []string, chars string) (ans int) {
cnt := [26]int{}
for _, c := range chars {
cnt[c-'a']++
}
for _, w := range words {
wc := [26]int{}
ok := true
for _, c := range w {
c -= 'a'
wc[c]++
if wc[c] > cnt[c] {
ok = false
break
}
}
if ok {
ans += len(w)
}
}
return
}class Solution {
/**
* @param String[] $words
* @param String $chars
* @return Integer
*/
function countCharacters($words, $chars) {
$sum = 0;
for ($i = 0; $i < strlen($chars); $i++) {
$hashtable[$chars[$i]] += 1;
}
for ($j = 0; $j < count($words); $j++) {
$tmp = $hashtable;
$sum += strlen($words[$j]);
for ($k = 0; $k < strlen($words[$j]); $k++) {
if (!isset($tmp[$words[$j][$k]]) || $tmp[$words[$j][$k]] === 0) {
$sum -= strlen($words[$j]);
break;
}
$tmp[$words[$j][$k]] -= 1;
}
}
return $sum;
}
}Complexity comparison
| 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'. |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency Counting (Array) | O(W * K) | O(1) | Best choice when characters are limited (e.g., lowercase English letters). Fast lookups and minimal memory. |
| Map-based Character Counting | O(W * K) | O(K) | Useful when the character set is large or unknown and fixed-size arrays are not practical. |
Frequently asked questions
Is Find Words That Can Be Formed by Characters easy or hard?
Find Words That Can Be Formed by Characters is classified as an Easy problem on LeetCode with a high acceptance rate around 70%. The challenge mainly tests understanding of character counting, arrays, and hash maps rather than complex algorithms.
Find Words That Can Be Formed by Characters Python/Java solution
Python and Java implementations typically create an array or dictionary to store character frequencies of the given string. For each word, compute its frequency and verify it does not exceed the base counts. If valid, add the word length to the result. The algorithm remains O(W * K) in both languages.
How to solve Find Words That Can Be Formed by Characters in O(n)?
Build a frequency counter for the characters string, then iterate through each word and count its characters. For every character in the word, check if its frequency exceeds the available count. If all checks pass, add the word length to the answer. Since counting and comparisons are linear in word length, the overall complexity stays O(W * K).
What is the best approach for Find Words That Can Be Formed by Characters?
The most efficient approach uses character frequency counting with a fixed array of size 26. Count the frequency of characters in the input string and compare it with the frequency of each word. If every character in the word appears within the available count, add its length to the total. This approach runs in O(W * K) time and O(1) space.
Is Find Words That Can Be Formed by Characters asked at Google/Amazon/Meta?
Problems involving character frequency counting and hash maps frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern—verifying resource availability using frequency arrays—is a common interview concept.
What data structure is used in Find Words That Can Be Formed by Characters?
The typical solution uses a frequency array of size 26 to store counts of lowercase letters. Some implementations use a hash map instead, especially when the character set is not restricted. Both approaches rely on counting and quick lookup of character frequencies.
What is the time complexity of Find Words That Can Be Formed by Characters?
The time complexity is O(W * K), where W is the number of words and K is the average length of each word. Each word is scanned once to compute its character counts and compared against the base frequency array built from the characters string.