How to Find Words That Can Be Formed by Characters?

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.

Note:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

Hints:

• Solve the problem for each string in words independently.
• Now try to think in frequency of letters.
• Count how many times each character occurs in string chars.
• To form a string using characters from chars, the frequency of each character in chars must be greater than or equal the frequency of that character in the string to be formed.

Count the Frequency

We can count the frequencies for each letters (they are lower-case letters), and we can store them in a static int[26] array or hash map if the given characters are of broad ranges.

Then, we can go through the list of words, and check one by one if it can be formed by using the characters – reduce the frequency of a character and return false if it falls below zero.

The space complexity is constant O(1) as we only allocate a counter array with fixed size 26. The time complexity is O(Max(N, MO)) where N is the size of the input character set i.e. chars, and the M is the number of words in the list, and the O is the average size of the words in the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int ans = 0;
        int count[26];
        std::fill(begin(count), end(count), 0);
        for (const auto &n: chars) {
            count[n - 97] ++;
        }
        for (const auto &s: words) {
            int cc[26];
            std::copy(begin(count), end(count), begin(cc));
            if (canWordBeFormedBy(s, cc)) {
                ans += s.size();
            }
        }
        return ans;
    }
private:
    bool canWordBeFormedBy(const string &s, int count[26]) {
        for (const auto &n: s) {
            if (count[n - 97] == 0) {
                return false;
            }
            count[n - 97] --;
        }
        return true;
    }
};

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int ans = 0;
        int count[26];
        std::fill(begin(count), end(count), 0);
        for (const auto &n: chars) {
            count[n - 97] ++;
        }
        for (const auto &s: words) {
            int cc[26];
            std::copy(begin(count), end(count), begin(cc));
            if (canWordBeFormedBy(s, cc)) {
                ans += s.size();
            }
        }
        return ans;
    }
private:
    bool canWordBeFormedBy(const string &s, int count[26]) {
        for (const auto &n: s) {
            if (count[n - 97] == 0) {
                return false;
            }
            count[n - 97] --;
        }
        return true;
    }
};

Here, we use the std::fill to initialise the counter array to all zeros. And std::copy to copy an array to another in C++.

–EOF (The Ultimate Computing & Technology Blog) —