题目描述
给你一个字符串 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
的 分数最小。
请你返回替换所有问号 '?'
之后且分数最小的字符串。如果有多个字符串的 分数最小,那么返回字典序最小的一个。
样例
输入:s = "???"
输出: "abc"
解释:这个例子中,我们将 s 中的问号 '?' 替换得到 "abc"。
对于字符串 "abc",cost(0) = 0,cost(1) = 0 和 cost(2) = 0。
"abc" 的分数为 0。
其他修改 s 得到分数 0 的字符串为 "cba","abz" 和 "hey"。
这些字符串中,我们返回字典序最小的。
输入: 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^5
s[i]
要么是小写英文字母,要么是'?'
。
算法
(贪心,堆) $O(n \log |\Sigma|)$
- 显然,每种字母在最后统计答案的时候都是独立计算的。一个显然的思路是尽可能的让字符串中的字母出现次数平均。
- 预处理原始字符串中每种字母的出现次数,然后维护一个小根堆,存储字母已经出现的次数。
- 遍历字符串,遇到
'?'
时,从小根堆中弹出出现次数最少的字母,并记录这个字母需要被额外替换一次。然后把这个字母的出现次数加一后重新插入堆中。 - 由于替换字符的出现顺序不影响最后的答案,为了使得字典序最小,从前往后遍历字符串,按照字典序依次替换
'?'
为记录的字符。
时间复杂度
- 预处理的时间复杂度为 $O(n \log |\Sigma|)$。
- 第一次遍历字符串的时间复杂度为 $O(n \log |\Sigma|)$。
- 第二次遍历字符串的时间复杂度为 $O(n + |\Sigma|)$。
- 故时间复杂度为 $O(n \log |\Sigma|)$。
空间复杂度
- 需要 $O(|\Sigma|)$ 的额外空间存储频率数组和堆。
C++ 代码
class Solution {
public:
string minimizeStringValue(string s) {
vector<int> cnt(26, 0);
for (char c : s)
if (c != '?')
++cnt[c - 'a'];
priority_queue<pair<int, int>> heap;
for (int i = 0; i < 26; i++) {
heap.push(make_pair(-cnt[i], -i));
cnt[i] = 0;
}
for (char c : s) {
if (c != '?')
continue;
auto top = heap.top();
heap.pop();
++cnt[-top.second];
--top.first;
heap.push(top);
}
const int n = s.size();
for (int i = 0, j = 0; i < n; i++) {
if (s[i] != '?')
continue;
while (cnt[j] == 0)
++j;
s[i] = j + 'a';
--cnt[j];
}
return s;
}
};