Unique Mailbox Sequence Identification

Farmer John is taking a walk along a road lined with N farms. Unfortunately, the farms are not numbered, making it hard for him to know his exact position. However, each farm has a mailbox painted with a color represented by a letter from A to Z. By looking at the colors of consecutive mailboxes, Farmer John hopes to pinpoint his location uniquely.

The mailbox colors along the road are given as a string of length N consisting of uppercase letters. Farmer John wishes to determine the smallest integer K such that every contiguous subsequence (or window) of K mailbox colors in the string is unique. In other words, if you take any segment of K consecutive mailboxes, that sequence appears only once in the entire string.

This can be summarized mathematically: Let the mailbox sequence be represented as a string S of length N, and consider all substrings of length $$K$$. Find the minimum integer $$K$$ such that for all valid indices i and j with \(1 \leq i < j \leq N-K+1\), we have $$ S[i \ldots i+K-1] \neq S[j \ldots j+K-1]. $$

For example, for the mailbox sequence ABCDABC, if K = 3, the subsequence ABC appears twice. However, when K = 4, every contiguous block of 4 colors is unique. Therefore, the answer for that sequence is 4.

inputFormat

The input consists of two lines:

• The first line contains an integer N representing the number of farms.
• The second line contains a string of length N consisting of uppercase letters (A-Z) representing the mailbox colors along the road.

outputFormat

Output the smallest integer K such that every contiguous sequence of K mailbox colors is unique.

sample

7
ABCDABC

4