Де я?

Фермер Джон вийшов прогулятися дорогою і думає, що тепер він може заблукати!

Вздовж дороги розташовано $n$ ферм. На жаль, на фермах немає номерів будинків, тому фермеру Джону важко визначити, де він перебуває на дорозі. Проте на кожній фермі є кольорова поштова скринька при дорозі, тому фермер Джон сподівається, що, якщо він подивиться на кольори сусідніх з ним поштових скриньок, то зможе однозначно визначити, де він є.

Кожен колір поштової скриньки визначається літерою в діапазоні $A\dots Z$, тому послідовність $n$ поштових скриньок можна подати рядком довжини $n$ із літер $A\dots Z$. Деякі поштові скриньки можуть мати однаковий колір. Фермер Джон хоче знайти таке найменше значення $k$, щоб, подивившись на будь-яку послідовність із $k$ послідовних поштових скриньок, він міг однозначно визначити розташування цієї послідовності на дорозі.

Нехай послідовність поштових скриньок вздовж дороги ABCDABC. Фермер Джон не може взяти k = 3, оскільки, якщо він бачить $ABC$, є два можливих місця на дорозі, де може бути така послідовність кольорів. Найменше значення k = 4, оскільки якщо він дивиться на будь-яку послідовність із $4$ поштових скриньок, ця послідовність кольорів однозначно визначає його місцезнаходження на дорозі.