思路（贪心 + 桶思想）

• 统计频次：用数组统计 $26$ 个字母的出现次数，记最高频次为 $f_{max}$，与其相等的任务个数为 $k$。

• 关键结论：最短时间

  $ans=\max(|tasks|,(f_{max}-1)*(n+1)+k)$

  • 解释：将最高频任务分成 $f_{max}$ 组，其中前 $f_{max}-1$ 组需要被 $n$ 的冷却间隔撑开，每组长度为 $(n+1)$（包含 $1$ 个最高频任务和 $n$ 个空位/其他任务）；最后再放入与 $f_{max}$ 持平的 $k$ 个任务收尾。若其他任务足以填满空位，则答案至少是 $|tasks|$。

• 复杂度：计数与扫描均为常数级字母表规模，整体 $O(|tasks|)$，空间 $O(26)$。

题目内容

给你一个用字符串 $tasks$ 表示的 $CPU$需要执行的任务列表，用字母$A$到$Z$表示，以及一个冷却周期$n$。每个周期允许完成一项任务。任务可以按任何顺序完成，但有一个限制:两个相同种类的任务之间必须有长度为$n$的冷却周期。返回完成所有任务所需要的最短周期数。

例$1$:对于$n=2$，任务列表$AAABBB$，其一种最优执行顺序为

$A->B->idle->A->B->idle->A->B$

上述执行序列满足任意$A$或$B$任务间都有$2$个周期的冷却，最短周期数为$8$

例$2$:对于$n=3$，任务列表$AAABBB$，其一种最优执行顺序为

$A->B->idle->idle->A->B->idle->idle->A->B$

上述执行序列满足任意$A$或$B$任务间都有$3$个周期的冷却，最短周期数为$10$

例$3$:对于$n=1$，任务列表$ACABDB$，其一种最优执行顺序为

$A->B->C->D->A->B$

上述执行序列满足任意同种任务间都有$1$个周期的冷却,最短周期数为$6$

输入描述

冷却周期$n$:$2<=n<10$

$task$字符串长度:长度$<400$

$task$字符串:仅包含大写字母

输出描述

成所有任务所需的最短周期数

样例1

输入

2
6
AAABBB

输出

8