← 返回题目列表

AtCoder · arc140_a

A. 右弦

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

对于字符串 T 由小写英文字母组成,考虑下面的问题,令 f(T) 就是答案。

求执行任意次以下操作得到的不同字符串的数量:删除第一个字符 T 并将其附加到末尾。

给你一个字符串 S 长度 N 由小写英文字母组成。您最多可以执行以下操作 K 次(可能为零)。

  • 选择一个字符 S 并将其更改为任意小写英文字母。

找到以下的最小可能值 f(S) 操作后。

约束

  • 1 \le N \le 2000
  • 0 \le K \le N
  • S 是一个长度为 N 由小写英文字母组成。
  • N 和 K 是整数。

输入

输入由标准输入按以下格式给出:

N K
S

输出

打印答案。


示例输入 1

4 1
abac

示例输出 1

2

如果更改第四个字符 c to b 在第一个操作中,您得到 S= abab,与 f(S)=2.

f(S) 无法制作 1 或更少的一次或更少的操作,所以答案是 2.


示例输入 2

10 0
aaaaaaaaaa

示例输出 2

1

示例输入 3

6 1
abcaba

示例输出 3

3