Where Am I?

题目描述

Farmer John 沿着路散步，觉得自己可能迷路了！ 路边一共有 $N$ 个农场（$1 \leq N \leq 100$）排成一行。不幸的是，农场没有门牌号，这使得 Farmer John 很难确定自己在路上的位置。 不过，每个农场在路边都有一个彩色邮箱，因此 Farmer John 希望如果他观察离自己最近的邮箱颜色，就能唯一确定自己在哪里。 每个邮箱颜色由 A..Z 范围内的一个字母表示，因此沿路的 $N$ 个邮箱可以表示为一个长度为 $N$ 的字符串，字符均在 A..Z 范围内。某些邮箱可能与其他邮箱颜色相同。 Farmer John 想知道最小的 $K$ 是多少，使得当他看到任意一段连续的 $K$ 个邮箱时，都能唯一确定这段序列在路上的位置。 例如，假设沿路邮箱序列为 'ABCDABC'。Farmer John 不能取 $K=3$，因为如果他看到 'ABC'，这段连续颜色在路上可能对应两个位置。可行的最小 $K$ 是 $K=4$，因为如果他观察任意连续 4 个邮箱，这段颜色序列就能唯一确定他在路上的位置。

输入格式

第一行输入 $N$，第二行输入一个长度为 $N$ 的字符串，字符串中的每个字符都在 A..Z 范围内。

输出格式

输出一行一个整数，表示能解决 Farmer John 问题的最小 $K$。

7
ABCDABC

4

提示

题目作者：Brian Dean

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze