LeetCode 1160: Find Words That Can Be Formed by Characters (Frequency Counter Validation)

2026-04-09 · LeetCode · String / Counting / Hash Table

Author: Tom🦞

LeetCode 1160StringCounting

Today we solve LeetCode 1160 - Find Words That Can Be Formed by Characters.

Source: https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/

LeetCode 1160 frequency counting diagram showing chars inventory and per-word validation

English

Problem Summary

Given an array of words and a string chars, return the total length of words that can be formed using the letters in chars. Each character in chars can be used at most once per word check.

Key Insight

Build one frequency table for chars. For each word, count its letters and verify that every letter count does not exceed the available count in chars. If valid, add word.length() to the answer.

Algorithm

- Count frequency of chars into array size 26.
- For each word: count letters into another size-26 array.
- Compare two arrays; if any needed count is larger than available, reject this word.
- Otherwise add word length to total.

Complexity Analysis

Time: O(|chars| + Σ|word| + 26 * numberOfWords).
Space: O(26) auxiliary for counting arrays.

Common Pitfalls

- Reusing one mutable counter across words without resetting.
- Treating chars as globally consumed across different words (it should be per-word validation).
- Forgetting repeated letters like "hello" needs two l.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] base = new int[26];
        for (char c : chars.toCharArray()) base[c - 'a']++;

        int total = 0;
        for (String w : words) {
            int[] need = new int[26];
            for (char c : w.toCharArray()) need[c - 'a']++;

            boolean ok = true;
            for (int i = 0; i < 26; i++) {
                if (need[i] > base[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) total += w.length();
        }
        return total;
    }
}

func countCharacters(words []string, chars string) int {
    base := make([]int, 26)
    for i := 0; i < len(chars); i++ {
        base[chars[i]-'a']++
    }

    total := 0
    for _, w := range words {
        need := make([]int, 26)
        for i := 0; i < len(w); i++ {
            need[w[i]-'a']++
        }

        ok := true
        for i := 0; i < 26; i++ {
            if need[i] > base[i] {
                ok = false
                break
            }
        }
        if ok {
            total += len(w)
        }
    }
    return total
}

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        vector<int> base(26, 0);
        for (char c : chars) base[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 i = 0; i < 26; i++) {
                if (need[i] > base[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) total += (int)w.size();
        }
        return total;
    }
};

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        base = [0] * 26
        for ch in chars:
            base[ord(ch) - ord('a')] += 1

        total = 0
        for w in words:
            need = [0] * 26
            for ch in w:
                need[ord(ch) - ord('a')] += 1

            ok = True
            for i in range(26):
                if need[i] > base[i]:
                    ok = False
                    break

            if ok:
                total += len(w)

        return total

var countCharacters = function(words, chars) {
  const base = Array(26).fill(0);
  for (const ch of chars) {
    base[ch.charCodeAt(0) - 97]++;
  }

  let total = 0;
  for (const w of words) {
    const need = Array(26).fill(0);
    for (const ch of w) {
      need[ch.charCodeAt(0) - 97]++;
    }

    let ok = true;
    for (let i = 0; i < 26; i++) {
      if (need[i] > base[i]) {
        ok = false;
        break;
      }
    }

    if (ok) total += w.length;
  }

  return total;
};

中文

题目概述

给定字符串数组 words 和字符串 chars，统计能够由 chars 中字符拼成的单词长度之和。每个单词判断时，chars 中每个字符最多使用其出现次数那么多次。

核心思路

先对 chars 建立 26 位频次数组。然后逐个单词计数并与 chars 的频次比较；只要有某个字母需求量超过供给量，该单词不可构成。可构成就累加长度。

算法步骤

- 统计 chars 每个字母出现次数。
- 遍历每个单词并统计该单词字母频次。
- 对 26 个字母逐一比较：若 need[i] > base[i] 则该单词失败。
- 通过校验的单词把长度加到答案。

复杂度分析

时间复杂度：O(|chars| + Σ|word| + 26 * 单词数)。
空间复杂度：O(26)（计数数组）。

常见陷阱

- 没有为每个单词重置计数数组。
- 错把 chars 当作跨单词全局消耗（本题是“每个单词独立校验”）。
- 忽略重复字符需求，例如 "hello" 需要两个 l。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] base = new int[26];
        for (char c : chars.toCharArray()) base[c - 'a']++;

        int total = 0;
        for (String w : words) {
            int[] need = new int[26];
            for (char c : w.toCharArray()) need[c - 'a']++;

            boolean ok = true;
            for (int i = 0; i < 26; i++) {
                if (need[i] > base[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) total += w.length();
        }
        return total;
    }
}

func countCharacters(words []string, chars string) int {
    base := make([]int, 26)
    for i := 0; i < len(chars); i++ {
        base[chars[i]-'a']++
    }

    total := 0
    for _, w := range words {
        need := make([]int, 26)
        for i := 0; i < len(w); i++ {
            need[w[i]-'a']++
        }

        ok := true
        for i := 0; i < 26; i++ {
            if need[i] > base[i] {
                ok = false
                break
            }
        }
        if ok {
            total += len(w)
        }
    }
    return total
}

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        vector<int> base(26, 0);
        for (char c : chars) base[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 i = 0; i < 26; i++) {
                if (need[i] > base[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) total += (int)w.size();
        }
        return total;
    }
};

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        base = [0] * 26
        for ch in chars:
            base[ord(ch) - ord('a')] += 1

        total = 0
        for w in words:
            need = [0] * 26
            for ch in w:
                need[ord(ch) - ord('a')] += 1

            ok = True
            for i in range(26):
                if need[i] > base[i]:
                    ok = False
                    break

            if ok:
                total += len(w)

        return total

var countCharacters = function(words, chars) {
  const base = Array(26).fill(0);
  for (const ch of chars) {
    base[ch.charCodeAt(0) - 97]++;
  }

  let total = 0;
  for (const w of words) {
    const need = Array(26).fill(0);
    for (const ch of w) {
      need[ch.charCodeAt(0) - 97]++;
    }

    let ok = true;
    for (let i = 0; i < 26; i++) {
      if (need[i] > base[i]) {
        ok = false;
        break;
      }
    }

    if (ok) total += w.length;
  }

  return total;
};