USACO 2019 - Dec - Bronze - Where Am I?

View as PDF

Submit solution

Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=964
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nông dân John đang đi dạo và anh ấy nghĩ mình đã bị lạc.

Trên đường đi có ~N~ nông trại ~(1 \leq N \leq 100)~. Mỗi nông trại không có số nhà, làm cho nông dân John khó mà biết được vị trí của anh ấy trên đường đi. Tuy nhiên, mỗi nông trại có một hòm thư rực rỡ ở bên đường, thế nên nông dân John hi vọng là nếu anh ấy nhìn màu của những hòm thư gần anh ấy nhất thì anh ấy có thể xác định được vị trí của mình.

Màu của mỗi hòm thứ được xác định bởi một kí tự trong khoảng A…Z, thế nên một dãy gồm ~N~ hòm thư có thể được thể hiện bằng một xâu có độ dài ~N~ chứa các kí tự trong khoảng A…Z. Một số hòm thư có thể có màu giống như các hòm thư khác. Nông dân John muốn tìm giá trị ~K~ nhỏ nhất mà nếu anh ấy nhìn ~K~ hòm thư liên tiếp bất kì thì chuỗi kí tự của ~K~ hòm thư ấy là phân biệt.

Ví dụ, nếu dãy hòm thư là ABCDABC. Nông dân John không thể chọn ~K=3~ vì nếu anh ấy thấy chuỗi ABC thì tồn tại 2 vị trí trên đường mà có chuỗi ABC. Giá trị ~K~ nhỏ nhất thỏa mãn là ~K=4~ vì nếu anh ấy nhìn 4 hòm thư liên tiếp bất kì thì mỗi chuỗi kí tự của 4 hòm thư là phân biệt.

Input

Dòng đầu tiên chứa số nguyên dương ~N~, dòng thứ hai chứa một xâu gồm ~N~ kí tự trong khoảng A…Z.

Output

In ra một số nguyên dương là ~K~ bé nhất thỏa mãn yêu cầu của John.

Sample Input

7
ABCDABC

Sample Output

4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.