Max Common Subset

Given a list of strings, find the size of the largest subset of strings such that every pair of strings in the subset has at least one common letter. Two strings are said to have a common letter if there exists at least one character that appears in both strings.

Formally, let the set of strings be \(S = \{s_1, s_2, \dots, s_N\}\). We need to find the maximum size \(M\) of a subset \(T \subseteq S\) such that for every two distinct strings \(s_i, s_j \in T\), we have \(s_i \cap s_j \neq \emptyset\) (i.e. they share at least one common letter).

You are given multiple test cases via standard input.

inputFormat

The input is read from standard input. It starts with a single integer \(N\) which represents the number of strings. The following \(N\) lines each contain one non-empty string composed of lowercase letters.

outputFormat

Output a single integer to standard output – the size of the largest subset satisfying the condition that every pair of strings share at least one common letter.

4
abcdefghijklmno
mnopqrstuvwxyz
ghijklmnopqrstuv
abcxyzdefmnop

4