시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 47 | 35 | 34 | 75.556% |
A set of words is called swap free if there is no way to turn any word in the set into any other word in the set by swapping only a single pair of (not necessarily adjacent) letters.
You are given a set of n words that are all anagrams of each other. There are no duplicate letters in any word. Find the size of the largest swap free subset of the given set. Note that it is possible for the largest swap free subset of the given set to be the set itself.
The first line of input contains a single integer n (1 ≤ n ≤ 500).
Each of the next n lines contains a single word w (1 ≤ |w| ≤ 26).
Every word contains only lower-case letters and no duplicate letters. All n words are unique, and every word is an anagram of every other word.
Output a single integer, which is the size of the largest swap free subset.
6 abc acb cab cba bac bca
3
11 alerts alters artels estral laster ratels salter slater staler stelar talers
8
6 ates east eats etas sate teas
4