Quick Overview

Given a list of words and a pool of letters, compute the total length of the words that can be spelled when each pool letter is used at most once per word. It tests character frequency counting, independent per-word checks, and correct handling of repeated letters and repeated words in the input.

Total Length of Words Buildable from a Limited Pool of Letters

Company: TabaPay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given a list of words and a string `chars` that acts as a pool of letters. A word is buildable if it can be spelled with letters from `chars`, where each letter of `chars` can be used at most once within that word. Each word is checked on its own against the full pool: building one word does not use up letters for the others. Return the total length of all buildable words. ### Function Signature ```python def total_buildable_length(words: list[str], chars: str) -> int: ``` ### Rules - A word is buildable when, for every letter, the number of times the letter occurs in the word is at most the number of times it occurs in `chars`. - Every element of `words` is checked independently against all of `chars`; letters are never consumed across words. - Repeated words in `words` are counted once per occurrence. - Return the sum of the lengths of the buildable words, or 0 if none is buildable. ### Constraints - `1 <= len(words) <= 1000` - `1 <= len(words[i]) <= 100` - `1 <= len(chars) <= 100` - Every string contains only lowercase English letters `a` to `z`. - The answer is at most 100,000. ### Examples **Example 1** ```text Input: words = ["dog", "god", "good", "do"], chars = "odgx" Output: 8 ``` The pool has one each of `o`, `d`, `g` and `x`. `"dog"`, `"god"` and `"do"` are buildable (3 + 3 + 2 = 8); `"good"` needs two `o`. **Example 2** ```text Input: words = ["hello", "world", "low", "owl"], chars = "lowrd" Output: 11 ``` `"hello"` needs `h` and `e`, which the pool lacks. `"world"`, `"low"` and `"owl"` are buildable: 5 + 3 + 3 = 11. **Example 3** ```text Input: words = ["aa", "a", "b", "a"], chars = "a" Output: 2 ``` `"aa"` needs two `a` and `"b"` needs a `b`. Each of the two `"a"` entries is checked separately against the full pool and counts: 1 + 1 = 2.

Overview: Given a list of words and a pool of letters, compute the total length of the words that can be spelled when each pool letter is used at most once per word. It tests character frequency counting, independent per-word checks, and correct handling of repeated letters and repeated words in the input.

You are given a list of strings `words` and a string `chars` that acts as a pool of letters. A word is **buildable** if it can be spelled with letters from `chars`, where each letter of `chars` can be used at most once within that word. Each word is checked on its own against the full pool: building one word does not use up letters for any other word. Implement `total_buildable_length(words, chars)`, which returns the total length of all buildable words. **Rules** - A word is buildable when, for every letter, the number of times the letter occurs in the word is at most the number of times it occurs in `chars`. - Every element of `words` is checked independently against all of `chars`; letters are never consumed across words. - Repeated words in `words` are counted once per occurrence. - Return the sum of the lengths of the buildable words, or `0` if none is buildable. **Example 1** ``` Input: words = ["dog", "god", "good", "do"], chars = "odgx" Output: 8 ``` The pool has one each of `o`, `d`, `g` and `x`. `"dog"`, `"god"` and `"do"` are buildable (3 + 3 + 2 = 8); `"good"` needs two `o`. **Example 2** ``` Input: words = ["aa", "a", "b", "a"], chars = "a" Output: 2 ``` `"aa"` needs two `a` and `"b"` needs a `b`. Each of the two `"a"` entries is checked separately against the full pool and counts: 1 + 1 = 2. **Constraints** - `1 <= len(words) <= 1000` - `1 <= len(words[i]) <= 100` - `1 <= len(chars) <= 100` - Every string contains only lowercase English letters `a` to `z`. - The answer is at most 100,000. The answer never exceeds 2^31 - 1, so a signed 32-bit integer return type is sufficient in every language.

Constraints

  • 1 <= len(words) <= 1000
  • 1 <= len(words[i]) <= 100
  • 1 <= len(chars) <= 100
  • Every string contains only lowercase English letters a to z.
  • The answer is at most 100,000.

Examples

Input: (['dog', 'god', 'good', 'do'], 'odgx')

Expected Output: 8

Explanation: Source example 1: 'dog', 'god' and 'do' are buildable (3 + 3 + 2); 'good' needs two 'o'.

Input: (['hello', 'world', 'low', 'owl'], 'lowrd')

Expected Output: 11

Explanation: Source example 2: 'hello' needs 'h' and 'e'; 'world', 'low' and 'owl' give 5 + 3 + 3.

Hints

  1. Whether a word can be built depends only on how many times each letter appears in the word compared with how many times it appears in chars.
  2. The pool is never used up: every word in the list, including each repeated copy, is compared against all of chars.
  3. A word can fail because it needs a letter that chars does not contain at all, or because it needs more copies of a letter than chars has.

Loading coding console...

Show the approach

Approach

Algorithm: count how many times each of the 26 letters occurs in chars once, into pool. Then, for each word, count its letters into a fresh 26-entry array need, stopping early as soon as some letter's need count exceeds its pool count. If the scan finishes without that happening, the word is buildable and its length is added to the total.

Invariant: after reading the first k letters of a word, need[c] equals the number of occurrences of c among those k letters. Counts only grow, so some letter's full-word count exceeds its pool count exactly when some prefix first pushes need[c] above pool[c]. The early exit therefore rejects precisely the words that break the rule (a word is buildable when every letter occurs in it at most as often as in chars), and every other word is accepted.

Correctness against the rules: pool is never modified, so each word is judged against the full pool and letters are never consumed across words. Every element of words is processed once per occurrence, so repeated words and anagrams each count. The total starts at 0, so if no word is buildable the answer is 0.

Edge cases: a letter that does not occur in chars has pool count 0, so any occurrence of it rejects the word; a word longer than chars must use some letter more often than chars holds it, so it is always rejected; a word exactly matching the pool's counts is accepted (the comparison is strictly greater-than). The answer is at most 100,000, so a 32-bit int never overflows.

Time complexity:
O(|chars| + L), where L is the total length of all words
Space complexity:
O(1) extra space (two 26-entry count arrays)