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

https://leetcode.cn/problems/replace-question-marks-in-string-to-minimize-its-value/description/

这题如果想清楚的话还是非常简单的。考虑一个情况就是比如下面这样的字符串

"z .. z .. ? z z ? "

假设两个问号里面只能填写一个z的话，其实填写在哪里是没有任何关系的。对于一个字符，cost完全取决于它在这个字符串里面出现多少次。

如果想清楚这个问题的话，那么算法就是将所有的字符平均使用，完了做一个排序确保字符串序是最小的。

class Solution:
    def minimizeStringValue(self, s: str) -> str:
        from collections import Counter
        cnt = Counter(list(s))

        ans = []
        sel = []
        for c in s:
            if c == '?':
                mv, mc = 1 << 30, None
                for idx in range(26):
                    c2 = chr(ord('a') + idx)
                    if cnt[c2] < mv:
                        mv = cnt[c2]
                        mc = c2
                cnt[mc] += 1
                sel.append(mc)
        sel.sort(reverse=True)
        for c in s:
            if c == '?':
                ans.append(sel.pop())
            else:
                ans.append(c)
        # print(ans)
        return ''.join(ans)