{"problem":{"name":"Right String","description":{"content":"For a string $T$ consisting of lowercase English letters, consider the question below, and let $f(T)$ be the answer. > Find the number of different strings obtained by performing the following operat","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc140_a"},"statements":[{"statement_type":"Markdown","content":"For a string $T$ consisting of lowercase English letters, consider the question below, and let $f(T)$ be the answer.\n\n> Find the number of different strings obtained by performing the following operation any number of times: delete the first character from $T$ and append it to the end.\n\nYou are given a string $S$ of length $N$ consisting of lowercase English letters. You can perform the operation below at most $K$ times (possibly zero).\n\n*   Choose a character of $S$ and change it to any lowercase English letter.\n\nFind the minimum possible value of $f(S)$ after your operations.\n\n## Constraints\n\n*   $1 \\le N \\le 2000$\n*   $0 \\le K \\le N$\n*   $S$ is a string of length $N$ consisting of lowercase English letters.\n*   $N$ and $K$ are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc140_a","tags":[],"sample_group":[["4 1\nabac","2\n\nIf you change the fourth character `c` to `b` in the first operation, you get $S=$ `abab`, with $f(S)=2$.\n$f(S)$ cannot be made $1$ or less in one or fewer operations, so the answer is $2$."],["10 0\naaaaaaaaaa","1"],["6 1\nabcaba","3"]],"created_at":"2026-03-03 11:01:13"}}