Problem A
Repetitive Song
Your younger sibling is obsessed with a fairly repetitive song. They claim that it is not repetitive, so you decided to prove your point by finding the longest (in terms of the number of words) subsequence of the song that your sibling cannot definitively identify within the full song lyrics.
More formally, a length-$\ell $ subsequence of a song with $n$ words is a tuple of $\ell $ integers $1 \leq s_1 < s_2 < \cdots < s_\ell \leq n$ identifying the words in the subsequence. The subsequence is non-identifiable if there exists a different length-$\ell $ subsequence $1 \leq t_1 < t_2 < \cdots < t_ L \leq n$ (with $s_ i \neq t_ i$ for at least one index $i$) where word $s_1$ in the song is identical to word $t_1$, word $s_2$ is identical to word $t_2$, etc.
Given the lyrics for a song, print the length of the longest non-identifiable subsequence.
Input
The first line of input contains a single integer $n$ ($1 \le n \leq 10^5$) specifying the number of words in the song lyrics.
Each of the next $n$ lines contains one word of the song lyrics, given in order. Each word consists of up to 20 uppercase (A–Z) and lowercase (a–z) letters. The same word may appear on multiple lines. If two words do not match exactly (including the use of upper and lower case) then they are considered to be different words.
Output
Output a single integer $\ell $, the number of words in the longest non-identifiable song subsequence. If all of the song’s subsequences are identifiable, print $0$. When determining if a subsequence is identifiable, treat two words in the lyrics as identical if each of their corresponding characters are identical (in other words, case does matter).
Sample Input 1 | Sample Output 1 |
---|---|
10 bow bow chick chicka chicka bow bow chick chicka chicka |
9 |
Sample Input 2 | Sample Output 2 |
---|---|
31 head shoulders knees and toes knees and toes head shoulders knees and toes knees and toes eyes and ears and mouth and nose head shoulders knees and toes knees and toes |
29 |