949. The Two Words That Share the Most
Given n words, print the length of the longest common prefix over ALL PAIRS of
them. Take the best pair, not all of them together.
flower flow flight feed -> 4 flow and flower share flow
dog racecar car -> 0
same same -> 4 two equal words share everything
ab abc abcd abcde -> 4
## This is not problem 937 and not problem 82
Problem 937 asks for the prefix shared by EVERY word, which on flower flow
flight feed is the empty string, length 0. Problem 82 asks for the prefix shared
by exactly two given lines. This asks for the best pair out of n, which on the
same input is 4. The three answers differ on the same data, and the difference is
the reason all three exist.
## The trie answer, and why it is not the one to write
Insert everything with a counter at each node, as in problem 948. A node with counter at least 2 is a prefix shared by at least two words, so the answer is the depth of the deepest node whose counter is at least 2. It works, it is linear, and it costs 208 bytes a node under the 26-slot layout, up to 400001 nodes at these limits, which is about 83 MB.
## Sorting is smaller and the proof is the lesson
Sort the words. Then compute the common prefix length of each ADJACENT pair and take the largest.
sort the words
best = 0
for i in 0 .. n-2:
k = length of the common prefix of w[i] and w[i+1]
best = max(best, k)
That is n - 1 comparisons instead of every pair, and no structure at all.
## Why looking only at neighbours cannot miss the answer
Write lcp(x, y) for the length of the common prefix. For three strings in
sorted order x <= y <= z:
lcp(x, z) = min( lcp(x, y), lcp(y, z) )
To see it, let d = lcp(x, z). The first d characters of x and z agree,
and y lies between them in order, so y must agree with both on those d
characters too: a string differing from x before position d would sort either
below x or above z. So lcp(x,y) and lcp(y,z) are both at least d.
Neither can exceed d while the other stays at least d, because if both were
larger then x and z would agree past d as well.
Extending along a sorted run, lcp(w[i], w[j]) for i < j is the MINIMUM of the
adjacent values between them. A minimum of a set is never larger than any member,
so no non-adjacent pair can beat every adjacent pair, and the maximum over
adjacent pairs is the maximum over all pairs.
## The boundaries
Two identical words share their whole length, so duplicates give the maximum possible answer rather than a special case. Words sharing nothing give 0, and 0 is a legal answer that must be printed rather than treated as "no pair found". Comparing two words of different lengths must stop at the shorter one.
## Cost
Sorting is O(n log n) comparisons of up to 20 characters. The adjacent pass is
O(total characters). Space is O(1) beyond the input, against about 83 MB for
the trie. Nothing overflows; the answer is at most 20.
Constraints - `2 ≤ n ≤ 20000` - Every word is 1 to 20 lowercase English letters. - Words may repeat, and two equal words count as a pair.
Input
The first line contains an integer n.
The next n lines each contain one word.
Output
Print one integer: the largest number of leading characters shared by any two of the given words. Print 0 if no two of them share even their first character.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.