#C12640. Constructible Words
Constructible Words
Constructible Words
You are given two lists: a list of words and a list of available character sets. Each character set is a string consisting of lowercase letters where each letter can be used only once when constructing a word. A word is considered constructible if there is at least one character set that contains every character required by the word in at least the needed frequency.
For example, consider the word apple
and the character set aelpp
. The character frequencies in apple
are: a:1, p:2, l:1, e:1, and the frequencies in aelpp
are: a:1, e:1, l:1, p:2. Since the character set has at least the required frequency of each letter, the word apple
can be constructed.
Your task is to determine the total number of words from the word list that can be constructed using at least one of the provided character sets.
Note: Each character set can be used for each word independently, but a character set cannot be partially used to cover multiple words in the same check. For each word, you just need to find one character set that can construct it.
inputFormat
The input is given via standard input (stdin) and has the following format:
n word1 word2 ... (n lines of words) m chars1 chars2 ... (m lines of character sets)
Here, n
represents the number of words and m
represents the number of character sets.
outputFormat
Output the number of words that can be constructed using any one of the character sets. The output should be printed to standard output (stdout) as a single integer followed by a newline.
## sample4
apple
banana
orange
grape
4
aelpp
aaabnn
ognera
grape
4
</p>