Find Words That Can Be Formed by Characters

Easy
659.

Find Words That Can Be Formed by Characters

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.

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 <= 1000
  • 1 <= words[i].length, chars.length <= 100
  • All strings consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} chars
 * @return {number}
 */
var countCharacters = function(words, chars) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 1 <= words[i].length, chars.length <= 100
  • All strings consist of lowercase English letters.

Hints for Find Words That Can Be Formed by Characters

  1. Hint 1

    Count the letters of chars once — the budget is the same for every word.

  2. Hint 2

    For each word, count its own letters and compare slot by slot.

  3. Hint 3

    Counts, not membership: "cook" needs two os.

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

  1. Build have[26] from chars.
  2. For each word, build need[26] and check need[c] <= have[c] for every letter.
  3. 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 have as words are matched treats chars as 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 total

Java

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