README.md

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

English Version

题目描述

给你一个字符串 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 <= 105
• s[i] 要么是小写英文字母，要么是 '?' 。

解法

方法一：贪心 + 优先队列

根据题目，我们可以发现，如果一个字母 $c$ 出现的次数为 $v$，那么它对答案贡献的分数为 $1 + 2 + \cdots + (v - 1) = \frac{v \times (v - 1)}{2}$。为了使得答案尽可能小，我们应该尽量替换问号为那些出现次数较少的字母。

因此，我们可以使用优先队列（小根堆）来维护每个字母的出现次数，每次取出出现次数最少的字母，将其记录到数组 $t$ 中，然后将其出现次数加一，再放回优先队列中。最后，我们将数组 $t$ 排序，然后遍历字符串 $s$，将每个问号依次替换为数组 $t$ 中的字母即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

class Solution:
    def minimizeStringValue(self, s: str) -> str:
        cnt = Counter(s)
        pq = [(cnt[c], c) for c in ascii_lowercase]
        heapify(pq)
        t = []
        for _ in range(s.count("?")):
            v, c = pq[0]
            t.append(c)
            heapreplace(pq, (v + 1, c))
        t.sort()
        cs = list(s)
        j = 0
        for i, c in enumerate(s):
            if c == "?":
                cs[i] = t[j]
                j += 1
        return "".join(cs)

class Solution {
    public String minimizeStringValue(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        int k = 0;
        char[] cs = s.toCharArray();
        for (char c : cs) {
            if (c == '?') {
                ++k;
            } else {
                ++cnt[c - 'a'];
            }
        }
        PriorityQueue<int[]> pq
            = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        for (int i = 0; i < 26; ++i) {
            pq.offer(new int[] {cnt[i], i});
        }
        int[] t = new int[k];
        for (int j = 0; j < k; ++j) {
            int[] p = pq.poll();
            t[j] = p[1];
            pq.offer(new int[] {p[0] + 1, p[1]});
        }
        Arrays.sort(t);

        for (int i = 0, j = 0; i < n; ++i) {
            if (cs[i] == '?') {
                cs[i] = (char) (t[j++] + 'a');
            }
        }
        return new String(cs);
    }
}

class Solution {
public:
    string minimizeStringValue(string s) {
        int cnt[26]{};
        int k = 0;
        for (char& c : s) {
            if (c == '?') {
                ++k;
            } else {
                ++cnt[c - 'a'];
            }
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        for (int i = 0; i < 26; ++i) {
            pq.push({cnt[i], i});
        }
        vector<int> t(k);
        for (int i = 0; i < k; ++i) {
            auto [v, c] = pq.top();
            pq.pop();
            t[i] = c;
            pq.push({v + 1, c});
        }
        sort(t.begin(), t.end());
        int j = 0;
        for (char& c : s) {
            if (c == '?') {
                c = t[j++] + 'a';
            }
        }
        return s;
    }
};

func minimizeStringValue(s string) string {
	cnt := [26]int{}
	k := 0
	for _, c := range s {
		if c == '?' {
			k++
		} else {
			cnt[c-'a']++
		}
	}
	pq := hp{}
	for i, c := range cnt {
		heap.Push(&pq, pair{c, i})
	}
	t := make([]int, k)
	for i := 0; i < k; i++ {
		p := heap.Pop(&pq).(pair)
		t[i] = p.c
		p.v++
		heap.Push(&pq, p)
	}
	sort.Ints(t)
	cs := []byte(s)
	j := 0
	for i, c := range cs {
		if c == '?' {
			cs[i] = byte(t[j] + 'a')
			j++
		}
	}
	return string(cs)
}

type pair struct{ v, c int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v || h[i].v == h[j].v && h[i].c < h[j].c }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }