Substring appearing twice

You are given a string $S$ of lowercase English letters.

Define the following value: the length of the longest substring that occurs at two different starting positions in $S$. The two occurrences may overlap. If no such substring exists, the value is $0$.

You may replace a letter of $S$ with any other lowercase letter, and you may do this at most $K$ times. After every replacement is made, the value above is computed on the resulting string. Find the largest value you can reach.

Replacements apply to the string itself, once. When the two occurrences overlap, the letters inside the overlap are shared by both occurrences.

The first line contains the integer $K$ ($0 \le K \le 5000$).

The second line contains the string $S$, made of lowercase English letters only ($1 \le |S| \le 5000$).

Print one integer, the largest value reachable with at most $K$ replacements.

Take $K = 1$ and $S$ equal to abcba. Changing the third letter c to a gives ababa, where the substring aba occurs at position 0 and at position 2. The answer is 3.