Word Formation Algorithm using Hash Map

Given a list of strings words and a string letters, return the length of longest string in words that can be made from letters in letters. If no word can be made, return 0.

Note that you can’t reuse letters.
Constraints
n ≤ 10,000 where n is the length of words
m ≤ 1,000 where m is the length of letters
Example 1
Input
words = [“the”, “word”, “love”, “scott”, “finder”, “dictionary”]
letters = “fanierdow”
Output
6
Explanation
We can make the word finder out of our letters, which has the longest length of 6.

Example 2
Input
words = [“credit”, “nirvana”, “karma”, “empathy”, “hang”, “aaaaaaaaa”]
letters = “afnvlfkm”
Output
0
Explanation
We can’t make any of these words with the letters we have.

Word Formation Algorithm using Hash Map

We can count the letter frequencies in the given letters then iterate the words in the list, to see if each word can be made from the letters. We can use hash maps to store the letter frequencies of each and simulate the process of building it – taking one letter at a time until there is no enough letter or the word is built. The following time complexity is O(N(Max(M, L)) where N is the number of words in the list, and the M is the average word length, L is the length of given letter. The space complexity is O(L).

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

int wordFormation(vector<string>& words, string letters) {
    function<bool(string &, string &)> check = [&](string &a, string &letters) {
        unordered_map<char, int> count;        
        for (auto &n: letters) {
            count[n] ++;
        }
        for (auto &n: a) {
            if (count[n] -- == 0) return false;
        }
        return true;
    };
    int ans = 0;
    for (auto &n: words) {
        if (check(n, letters)) {
            ans = max(ans, (int)n.size());
        }
    }
    return ans;
}

int wordFormation(vector<string>& words, string letters) {
    function<bool(string &, string &)> check = [&](string &a, string &letters) {
        unordered_map<char, int> count;        
        for (auto &n: letters) {
            count[n] ++;
        }
        for (auto &n: a) {
            if (count[n] -- == 0) return false;
        }
        return true;
    };
    int ans = 0;
    for (auto &n: words) {
        if (check(n, letters)) {
            ans = max(ans, (int)n.size());
        }
    }
    return ans;
}

We don't need to build a hash map from the given letters at each iteration, instead, we can just build it once and use it to check all 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

int wordFormation(vector<string>& words, string letters) {
    unordered_map<char, int> count;        
    for (auto &n: letters) {
        count[n] ++;
    }
    function<bool(string &)> check = [&](string &a) {
        auto data = count;
        for (auto &n: a) {
            if (data[n] -- == 0) return false;
        }
        return true;
    };
    int ans = 0;
    for (auto &n: words) {
        if (check(n)) {
            ans = max(ans, (int)n.size());
        }
    }
    return ans;
}

int wordFormation(vector<string>& words, string letters) {
    unordered_map<char, int> count;        
    for (auto &n: letters) {
        count[n] ++;
    }
    function<bool(string &)> check = [&](string &a) {
        auto data = count;
        for (auto &n: a) {
            if (data[n] -- == 0) return false;
        }
        return true;
    };
    int ans = 0;
    for (auto &n: words) {
        if (check(n)) {
            ans = max(ans, (int)n.size());
        }
    }
    return ans;
}

The time complexity is O(NM) and the space complexity is O(L).

Using Python, we can get a shorter implementation by using the Counter object to store the letters (as keys) and their frequencies in the string. Then, we can use the AND operator to check if a string can be built from another string/letters.

1
2
3
4
5
6
7
8
9

class Solution:
    def wordFormationAlgorithm(self, words, letters):
        lc = Counter(letters)
        maxL = 0
        for w in words:
            wc = Counter(w)
            if wc == (wc & lc):
                maxL = max(maxL, len(w))
        return maxL  

class Solution:
    def wordFormationAlgorithm(self, words, letters):
        lc = Counter(letters)
        maxL = 0
        for w in words:
            wc = Counter(w)
            if wc == (wc & lc):
                maxL = max(maxL, len(w))
        return maxL  

--EOF (The Ultimate Computing & Technology Blog) --