374字符串权值最小化分割问题

题解

问题描述

小 G 定义了一个字符串的权值为：字符串的长度乘以字符串中不同字母的种类数量。现在，小 G 有一个字符串，她希望将这个字符串切分成 k 个子串，并希望这些子串的最大权值尽可能小。你需要帮助小 G 找到最优的切分方案，使得这 k 个子串中的最大权值最小化。

解题思路

看见最大值最小化直接二分答案，然后判断是否能够切分成 k 个子串。
check的时候，遍历字符串，用一个集合记录当前子串的不同字母，如果当前子串的不同字母数量乘以当前子串的长度大于 mid，则说明需要切分，切分的次数加一。
最后判断切分的次数是否大于 k，如果大于 k，说明 mid 太小，需要增大，否则减小。

实现代码

def solution(s: str, k: int) -> int:
    n = len(s)
    l, r = 1, 26 * n

    def check(mid):
        d = set()
        cnt = length = 0
        for i in range(n):
            length += 1
            d.add(s[i])
            if len(d) * length > mid:
                length = 1
                d = set({s[i]})
                cnt += 1
        return cnt + 1 > k

    while l <= r:
        mid = l + r >> 1
        if check(mid):
            l = mid + 1
        else:
            r = mid - 1
    return l

if __name__ == '__main__':
    print(solution("ababbbb", 2) == 6)
    print(solution("abcabcabc", 3) == 9)
    print(solution("aaabbbcccddd", 4) == 3)

复杂度分析

• 时间复杂度：

  • 二分查找的时间复杂度为 O(log (26 * n))。
  • 每次 check 调用的时间复杂度为 O(n)，因为需要遍历整个字符串。
  • 因此，总的时间复杂度为 O(n log (26 * n))。

• 空间复杂度：

  • 使用了常数级别的额外空间，空间复杂度为 O(1)。