替换字符串中的问号使分数最小

标签: 贪心哈希表字符串计数排序堆（优先队列）

难度: Medium

给你一个字符串 s 。s[i] 要么是小写英文字母，要么是问号 '?' 。

对于长度为 m 且只含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同字符出现的次数。

字符串 t 的分数为所有下标 i 的 cost(i) 之和。

比方说，字符串 t = "aab" ：

cost(0) = 0
cost(1) = 1
cost(2) = 0
所以，字符串 "aab" 的分数为 0 + 1 + 0 = 1 。

你的任务是用小写英文字母替换 s 中所有问号，使 s 的分数最小。

请你返回替换所有问号 '?' 之后且分数最小的字符串。如果有多个字符串的 分数最小 ，那么返回字典序最小的一个。

示例 1：

输入：s = "???"

输出： "abc"

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abc" 。

对于字符串 "abc" ，cost(0) = 0 ，cost(1) = 0 和 cost(2) = 0 。

"abc" 的分数为 0 。

其他修改 s 得到分数 0 的字符串为 "cba" ，"abz" 和 "hey" 。

这些字符串中，我们返回字典序最小的。

示例 2：

输入： s = "a?a?"

输出： "abac"

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abac" 。

对于字符串 "abac" ，cost(0) = 0 ，cost(1) = 0 ，cost(2) = 1 和 cost(3) = 0 。

"abac" 的分数为 1 。

提示：

1 <= s.length <= 10⁵
s[i] 要么是小写英文字母，要么是 '?' 。

Submission

运行时间: 157 ms

内存: 18.2 MB

chars = "abcdefghijklmnopqrstuvwxyz?"
uni2chr = [ch for ch in chars]
chr2uni = {ch:i for i,ch in enumerate(uni2chr)}

class Solution:
    def minimizeStringValue(self, s: str) -> str:

        # 统计字符数量
        cntS = Counter(s)
        cnt = [0] * 26
        anums = cntS["?"]
        if anums == 0: return s
        for ch, nums in cntS.items():
            if ch != "?": cnt[ord(ch) - 97] = nums

        # 计算出最不可能填入的最大数量
        queue = sorted(range(26), key=lambda it: cnt[it])

        index = 0
        highs = 0
        total = 0
        while index < 26 and cnt[queue[index]] * index - highs < anums:
            highs += cnt[queue[index]]
            index += 1

        # 计算出前一个高度下，需要填入的面积和最后一个高度
        lastH = cnt[queue[index - 1]]
        lastAll = anums - (lastH * index - highs)
        lower = lastAll // index + lastH
        preW = lastAll % index

        # 再次排序并根据最后一个高度计算具体需要填入的数量
        finalChar = []
        finalNums = []
        queue = sorted(queue[:index])
        for j in queue[:preW]:
            # j = queue[i]
            if lower + 1 - cnt[j] > 0:
                finalChar.append(chr(97 + j))
                finalNums.append(lower + 1 - cnt[j])
        for j in queue[preW:]:
        # for i in range(preW, index):
        #     j = queue[i]
            if lower - cnt[j] > 0:
                finalChar.append(chr(97 + j))
                finalNums.append(lower - cnt[j])

        # 依次填入
        ans = list(s)
        index = 0
        curChar = ""
        curNums = 0
        for i, ch in enumerate(ans):
            if ch != "?": continue
            if curNums == 0:
                curChar = finalChar[index]
                curNums = finalNums[index]
                index += 1
            ans[i] = curChar
            curNums -= 1
        return "".join(ans)

Explain

题解通过计算每个字符出现的频率来确定替换问号时最优的字符选择，以确保总分数最小。首先，统计字符串s中每个字符的数量，然后根据字符出现的频率排序，这样可以先填入出现次数少的字符，确保增加的分数最小。通过计算需要替换的问号数量和每个字母的出现次数，来确定每个字母填充问号后能达到的最低可能高度，以及最后一个高度。最后根据这些计算结果，构建最终的字符串，替换所有问号。

时间复杂度: O(n)

空间复杂度: O(n)

chars = 'abcdefghijklmnopqrstuvwxyz?'
uni2chr = [ch for ch in chars]
chr2uni = {ch:i for i,ch in enumerate(uni2chr)}

class Solution:
    def minimizeStringValue(self, s: str) -> str:
        from collections import Counter
        # 统计字符数量
        cntS = Counter(s)
        cnt = [0] * 26
        anums = cntS['?']
        if anums == 0: return s
        for ch, nums in cntS.items():
            if ch != '?': cnt[ord(ch) - 97] = nums

        # 计算出最不可能填入的最大数量
        queue = sorted(range(26), key=lambda it: cnt[it])

        index = 0
        highs = 0
        total = 0
        while index < 26 and cnt[queue[index]] * index - highs < anums:
            highs += cnt[queue[index]]
            index += 1

        # 计算出前一个高度下，需要填入的面积和最后一个高度
        lastH = cnt[queue[index - 1]]
        lastAll = anums - (lastH * index - highs)
        lower = lastAll // index + lastH
        preW = lastAll % index

        # 再次排序并根据最后一个高度计算具体需要填入的数量
        finalChar = []
        finalNums = []
        queue = sorted(queue[:index])
        for j in queue[:preW]:
            if lower + 1 - cnt[j] > 0:
                finalChar.append(chr(97 + j))
                finalNums.append(lower + 1 - cnt[j])
        for j in queue[preW:]:
            if lower - cnt[j] > 0:
                finalChar.append(chr(97 + j))
                finalNums.append(lower - cnt[j])

        # 依次填入
        ans = list(s)
        index = 0
        curChar = ''
        curNums = 0
        for i, ch in enumerate(ans):
            if ch != '?': continue
            if curNums == 0:
                curChar = finalChar[index]
                curNums = finalNums[index]
                index += 1
            ans[i] = curChar
            curNums -= 1
        return ''.join(ans)

Explore

算法首先统计了所有非问号字符的出现频率，并将这些频率存储在一个数组中。接着，算法通过一个`queue`列表，这个列表基于字符出现的次数进行排序，使得出现次数最少的字符排在前面。根据这个排序，算法尝试填充问号，优先填充出现次数少的字符。这是因为填充出现次数少的字符可以最小化可能的分数增加，即增加分布的均匀性，从而尽可能减少最高频率字符的出现次数，使总分数尽可能低。

这一步骤通过将字符按照出现次数进行升序排序，决定了填充问号的顺序。排序结果`queue`中，索引最低的是出现次数最少的字符。选择出现次数少的字符填充问号的原因是，这样可以在尽量不增加已经频繁出现的字符的同时，增加字符串中的字符多样性。这种策略有助于保持字符出现频率的平衡，从而达到最小化最终字符串中任何字符达到过高频率的风险，这是因为高频率的字符出现次数如果过多，会导致总分数增加。

这个计算步骤是为了确定在达到最后一个高度之前，还需要填充多少问号。其中`lastH`是当前已处理字符中出现次数最多的字符的数量，`index`是参与排序并计算的字符数，`highs`是到目前为止已处理的所有字符的累计出现次数。`lastAll`计算的是在达到最后一个高度前，还需要填充的问号数量。这个值是通过从总问号数`anums`中减去已经通过较低高度字符填充的区域面积来得出的。这个计算有助于确定如何分配剩余的问号，以确保填充后的字符串字符频率尽可能平衡。