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.

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7


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

Solution

Method 1 – Frequency Counting

Intuition

We count the frequency of each character in chars and for each word, check if it can be formed using the available characters (each used at most once).

Approach

  1. Count the frequency of each character in chars.
  2. For each word in words:
    • Count the frequency of each character in the word.
    • For each character, check if its count in the word is less than or equal to its count in chars.
    • If so, add the word’s length to the answer.
  3. Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        vector<int> cnt(26, 0);
        for (char c : chars) cnt[c - 'a']++;
        int ans = 0;
        for (auto& w : words) {
            vector<int> wc(26, 0);
            for (char c : w) wc[c - 'a']++;
            bool good = true;
            for (int i = 0; i < 26; ++i) {
                if (wc[i] > cnt[i]) { good = false; break; }
            }
            if (good) ans += w.size();
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func countCharacters(words []string, chars string) int {
    cnt := make([]int, 26)
    for _, c := range chars {
        cnt[c-'a']++
    }
    ans := 0
    for _, w := range words {
        wc := make([]int, 26)
        for _, c := range w {
            wc[c-'a']++
        }
        good := true
        for i := 0; i < 26; i++ {
            if wc[i] > cnt[i] {
                good = false
                break
            }
        }
        if good {
            ans += len(w)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] cnt = new int[26];
        for (char c : chars.toCharArray()) cnt[c - 'a']++;
        int ans = 0;
        for (String w : words) {
            int[] wc = new int[26];
            for (char c : w.toCharArray()) wc[c - 'a']++;
            boolean good = true;
            for (int i = 0; i < 26; i++) {
                if (wc[i] > cnt[i]) { good = false; break; }
            }
            if (good) ans += w.length();
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countCharacters(words: Array<String>, chars: String): Int {
        val cnt = IntArray(26)
        for (c in chars) cnt[c - 'a']++
        var ans = 0
        for (w in words) {
            val wc = IntArray(26)
            for (c in w) wc[c - 'a']++
            var good = true
            for (i in 0 until 26) {
                if (wc[i] > cnt[i]) { good = false; break }
            }
            if (good) ans += w.length
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def countCharacters(self, words: list[str], chars: str) -> int:
        from collections import Counter
        cnt = Counter(chars)
        ans = 0
        for w in words:
            wc = Counter(w)
            if all(wc[c] <= cnt[c] for c in wc):
                ans += len(w)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn count_characters(words: Vec<String>, chars: String) -> i32 {
        let mut cnt = [0; 26];
        for c in chars.chars() {
            cnt[c as usize - 'a' as usize] += 1;
        }
        let mut ans = 0;
        for w in words {
            let mut wc = [0; 26];
            for c in w.chars() {
                wc[c as usize - 'a' as usize] += 1;
            }
            let mut good = true;
            for i in 0..26 {
                if wc[i] > cnt[i] { good = false; break; }
            }
            if good { ans += w.len() as i32; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    countCharacters(words: string[], chars: string): number {
        const cnt = Array(26).fill(0);
        for (const c of chars) cnt[c.charCodeAt(0) - 97]++;
        let ans = 0;
        for (const w of words) {
            const wc = Array(26).fill(0);
            for (const c of w) wc[c.charCodeAt(0) - 97]++;
            let good = true;
            for (let i = 0; i < 26; i++) {
                if (wc[i] > cnt[i]) { good = false; break; }
            }
            if (good) ans += w.length;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(N * L), where N is the number of words and L is the average word length, since we count characters for each word.
  • 🧺 Space complexity: O(1), since the alphabet size is constant (26).