1830. The Shortest Piece That Appears Only Once
Print the length of the shortest piece of s that occurs exactly once, and the
SMALLEST position at which such a piece of that length begins.
An answer always exists, because the whole string occurs exactly once.
banana -> 1 0 b appears once
aaaa -> 4 0 nothing is unique until the whole string
abab -> 2 1 ba appears once; neither a nor b does
aab -> 1 2 b appears once, and 2 is the smallest such position
aabaabaab -> 5 2
Look at abab. No single character is unique. Of the three pieces of length 2,
ab appears twice and ba once, so the answer is 2 1. Reporting position 0
because it is the first position scanned is wrong; the smallest position of a
UNIQUE piece is wanted.
## What most people try first
For every length and every position, count how many times that piece occurs.
That is O(n^3) character work, beyond 10^15 at n = 200000. Even fixing one
length and comparing all pairs is O(n^2 k). The method below is
O(n log^2 n), about 6.5 * 10^7.
## The property is monotone, so binary search it
If some piece of length L is unique and L < n, then some piece of length
L + 1 is unique too: extend that piece by one character, on the right if there
is room and otherwise on the left. Any second occurrence of the longer piece
would contain a second occurrence of the shorter one, which does not exist.
So "some piece of length L is unique" is false up to some point and true from
there on, and the smallest such L can be binary searched.
lo = 1; hi = n
while lo < hi:
mid = (lo + hi) / 2
if unique(mid) exists: hi = mid
else: lo = mid + 1
answer = lo, and the position unique(lo) reports
Note that this midpoint is (lo + hi) / 2 and NOT (lo + hi + 1) / 2, because
this search moves hi down rather than lo up. Using the other one here spins
forever, and using this one in a search that moves lo up spins as well.
## Testing one length
Hash every window, count how many times each value occurs, then scan positions upwards and return the first whose value occurs exactly once.
## HASHING IS NOT EXACT, SO HERE IS THE PROBABILITY
TWO hashes are used, with different bases and different prime moduli near
10^9, packed into one 64 bit key. A false equality has probability about
10^-18 per pair, and a run implicitly compares fewer than about 4 * 10^11
pairs across all its rounds, so the chance of any error is below 10^-6.
A collision would make two different pieces look equal and hide a unique one, so
the answer would come out too large. The result is correct with probability at
least 1 - 10^-6, not with certainty.
## Overflow
The packed key reaches about 10^18, needing 64 bits against the signed limit
9223372036854775807.
## Cost
O(n log^2 n) time, O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - an answer always exists, since the whole string occurs exactly once - occurring exactly once means once in total, counting occurrences that overlap each other, and a length with one position is wanted
Input
A single line containing the string s, of lowercase English letters.
Output
Print two integers separated by one space on one line: the shortest length at which some piece of s occurs exactly once, and the smallest starting position of such a piece of that length.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.