题解：二分答案+哈希表check

题目是要最小化最大值，显然，设最终的答案为mid，显然，mid越大，越容易划分成k个子串，反之，则越困难。

在check当前答案mid是否满足条件时，我们可以看是否有一种划分策略，可以将字符串s至多换分成k个，使得每一个部分的权值都$\le mid$，为什么是至多，因为如果最终划分成的字符串数量$<k$，我们可以将子串做拆分，使得最终的字符串数量$=k$，但是反之，如果划分的字符串数量已经$>k$，那就说明当前mid无法满足条件。check的过程中可以使用哈希表来计算权值。

C++

题目内容

小红是一个喜欢安静的程序员，但他的室友却是一个爱说爱笑的应急食品。为了不被室友的声音打扰，小红自己设计了一副神奇的耳机，可以将外界的噪声转换成一些数字，然后用一种算法来过滤掉。你很好奇这种耳机是如何工作的，于是小红向你介绍了他的算法。

他的算法是这样的：首先，他将外界的声音转录成一个只包含小写字母的字符串 s ，然后计算这个字符串的权值 w(s) ，定义为 s 的长度乘以 s 中不同字母的个数。例如，$w(“abacb”) = 5 * 3 = 15$ 。然后，他将 s 切分成 k 个连续的子串 s1, s2, …, sk ，使得这 k 个子串中权值最大的那个尽可能小。这样，他就可以忽略掉那些权值较大的子串，只关注那些权值较小的子串，从而达到过滤噪声的目的。

你想试试这种算法，于是你输入了一个字符串 s 和一个正整数 k ，表示你想将 s 切分成 k 个子串。你需要输出切分后权值最大的子串的权值。你可以假设 s 的长度不超过 500000 ，且 k 不超过 s 的长度。

样例$1$

输入

adadasda
3

输出

8