Divisionals Spelling
InterviewTime limit1sMemory limit512 MB
Given n words and a contest with m questions labeled A onward, count how many words use only distinct letters from the first m letters.
- Level
Easy2 of 10
- Topics
- Implementation, String, Hash map
- Solved
- No attempts yet
Problem
Emilio's team is competing at the South Pacific ICPC Divisional Finals. They have read the problems and immediately know all the solutions. Emilio finds simply winning the contest boring. Instead, he has convinced his team to spell out a word with their submissions. He has put together a list of n words that he would like to spell.
Each question in the contest is labelled with an uppercase letter. The first question is labelled "A", the second is labelled "B", and so on. A word is spelled by solving questions in a specific order. For example, if Emilio's team wants to spell LEAK, the team first solves problem L, then problem E, then problem A, and finally problem K. The team may only solve each problem once, so they may not spell words with duplicated letters (for example, they cannot spell EMILIO). Which words can Emilio's team spell?
Input
The first line contains two integers n (1 ≤ n ≤ 100), which is the number of words in Emilio's list, and m (1 ≤ m ≤ 15), which is the number of questions in the contest.
The next n lines describe the words. Each of these lines contains a word with at least 1 and at most 15 uppercase letters. All the words are distinct.
Output
Display the number of words in the list that can be spelled.