会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
把报文 S 拆成恰好 m 个非空连续片段，最小化各片段「不同字母个数」的最大值。
- 设答案为 v。若上限 v 可行，则 v+1 也一定可行，可以在 [1,26]（实际只需到整串不同字母数）上二分最小的 v。
- 判定：每段不同字母不超过 v 时，最少要拆成几段。从左往右每次把当前段尽量拉长，直到再收一个新字母会超过 v，然后另起一段。段数 ≤m 即可。
- 题面要求恰好 m 段。若最少只要 k≤m 段，可以把某段再切开，干扰度不会变大，所以判定用「不超过 m 段」就够。m≤n，总能拆到单字符。
复杂度分析
题目内容
某通信台要把一条只含小写字母的报文 S（长度为 n）拆成恰好 m 个连续片段依次发出。每个片段必须非空，且按原顺序拼接后重新得到 S。
一个片段的干扰度，定义为该片段里出现过的不同字母个数。整次发送的干扰度，定义为这 m 个片段干扰度中的最大值。
请给出一种拆分方式，使整次发送的干扰度尽可能小，并输出这个最小可能值。
