407703: GYM102878 E Eigen Substring

For any string $$$s$$$, we define the substring $$$s\left[l..r\right]$$$ an eigen substring of $$$s$$$ if and only if $$$s\left[l..r\right]$$$ only appears once in $$$s$$$.

You are given a string $$$s$$$. Please calculate the length of the shortest eigen substring for each prefix of $$$s$$$.

The notation $$$s\left[l..r\right]$$$ represents the substring of $$$s$$$ that spans from the $$$l$$$-th character in $$$s$$$ to the $$$r$$$-th character in $$$s$$$, inclusive.

The input contains two lines.

The first line contains an integer $$$n$$$ $$$\left(1 \le n \le 10^6\right)$$$ which is the length of string $$$s$$$.

The second line contains the string $$$s$$$. It's guaranteed that all characters in $$$s$$$ are lowercase English letters.

Your output should contain $$$n$$$ lines. The $$$i$$$-th line of your output should contain one integer which denotes the length of the shortest eigen substring of $$$s\left[1..i\right]$$$.

5
ababb

1
1
1
2
2

For the example test case:

• The shortest eigen substring of $$$s\left[1..1\right] = \mathrm{a}$$$ is a;
• The shortest eigen substrings of $$$s\left[1..2\right] = \mathrm{ab}$$$ are a and b;
• The shortest eigen substring of $$$s\left[1..3\right] = \mathrm{aba}$$$ is b;
• The shortest eigen substring of $$$s\left[1..4\right] = \mathrm{abab}$$$ is ba;
• The shortest eigen substrings of $$$s\left[1..5\right] = \mathrm{ababb}$$$ are ba and bb.