Medium
题目描述
给你一个字符串 s。s[i] 要么是小写英文字母，要么是 '?'。
对于长度为 m 且只包含小写英文字母的字符串 t，我们定义索引 i 的函数 cost(i) 为在它之前（即范围 [0, i - 1]）出现的与 t[i] 相等的字符数量。
t 的值是所有索引 i 的 cost(i) 之和。
例如，对于字符串 t = "aab"：
cost(0) = 0cost(1) = 1cost(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。
其他一些值为 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^5s[i]要么是小写英文字母，要么是'?'。
解题思路
解题思路
这道题的核心思路是理解成本函数的计算方式和贪心策略。
首先分析成本函数：对于字符 c 出现 x 次，其总成本为 0 + 1 + 2 + … + (x-1) = x*(x-1)/2。这意味着字符出现次数越多，边际成本递增越快。
因此，要使总成本最小，我们应该尽可能平衡各字符的出现次数。具体策略分为两步：
确定替换字符：统计已有字符的频次，对于每个问号，选择当前频次最小的字符进行替换。可以用优先队列维护 26 个字母的频次，每次取出频次最小的字母。
保证字典序最小：虽然我们知道了要添加哪些字符，但为了保证结果字典序最小，需要将这些字符按字母序排列，然后从左到右依次填入问号位置。
算法步骤：
- 统计原字符串中各字母的出现频次
- 使用最小堆维护 26 个字母的频次
- 对于每个问号，选择频次最小的字母，并更新其频次
- 将选择的字母按字典序排序
- 从左到右将排序后的字母填入问号位置
这样既能保证总成本最小，又能保证字典序最小。
代码实现
class Solution {
public:
string minimizeStringValue(string s) {
vector<int> count(26, 0);
int questionMarks = 0;
// Count existing characters and question marks
for (char c : s) {
if (c != '?') {
count[c - 'a']++;
} else {
questionMarks++;
}
}
// Use priority queue to always pick the character with minimum frequency
priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;
for (int i = 0; i < 26; i++) {
pq.push({count[i], 'a' + i});
}
// Determine which characters to add
string toAdd = "";
for (int i = 0; i < questionMarks; i++) {
auto [freq, ch] = pq.top();
pq.pop();
toAdd += ch;
pq.push({freq + 1, ch});
}
// Sort the characters to add for lexicographical order
sort(toAdd.begin(), toAdd.end());
// Replace question marks with sorted characters
int addIndex = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '?') {
s[i] = toAdd[addIndex++];
}
}
return s;
}
};
class Solution:
def minimizeStringValue(self, s: str) -> str:
import heapq
count = [0] * 26
question_marks = 0
# Count existing characters and question marks
for c in s:
if c != '?':
count[ord(c) - ord('a')] += 1
else:
question_marks += 1
# Use heap to always pick the character with minimum frequency
heap = []
for i in range(26):
heapq.heappush(heap, (count[i], chr(ord('a') + i)))
# Determine which characters to add
to_add = []
for _ in range(question_marks):
freq, ch = heapq.heappop(heap)
to_add.append(ch)
heapq.heappush(heap, (freq + 1, ch))
# Sort the characters to add for lexicographical order
to_add.sort()
# Replace question marks with sorted characters
result = []
add_index = 0
for c in s:
if c == '?':
result.append(to_add[add_index])
add_index += 1
else:
result.append(c)
return ''.join(result)
public class Solution {
public string MinimizeStringValue(string s) {
int[] count = new int[26];
int questionMarks = 0;
// Count existing characters and question marks
foreach (char c in s) {
if (c != '?') {
count[c - 'a']++;
} else {
questionMarks++;
}
}
// Use priority queue to always pick the character with minimum frequency
var pq = new PriorityQueue<(int freq, char ch), int>();
for (int i = 0; i < 26; i++) {
pq.Enqueue((count[i], (char)('a' + i)), count[i]);
}
// Determine which characters to add
var toAdd = new List<char>();
for (int i = 0; i < questionMarks; i++) {
var (freq, ch) = pq.Dequeue();
toAdd.Add(ch);
pq.Enqueue((freq + 1, ch), freq + 1);
}
// Sort the characters to add for lexicographical order
toAdd.Sort();
// Replace question marks with sorted characters
var result = new char[s.Length];
int addIndex = 0;
for (int i = 0; i < s.Length; i++) {
if (s[i] == '?') {
result[i] = toAdd[addIndex++];
} else {
result[i] = s[i];
}
}
return new string(result);
}
}
var minimizeStringValue = function(s) {
const n = s.length;
const count = new Array(26).fill(0);
// Count existing letters
for (let i = 0; i < n; i++) {
if (s[i] !== '?') {
count[s[i].charCodeAt(0) - 97]++;
}
}
// Find replacements for question marks
const replacements = [];
const numQuestions = s.split('?').length - 1;
for (let i = 0; i < numQuestions; i++) {
let minCount = Math.min(...count);
let chosenChar = 0;
// Find lexicographically smallest char with minimum count
for (let j = 0; j < 26; j++) {
if (count[j] === minCount) {
chosenChar = j;
break;
}
}
replacements.push(String.fromCharCode(97 + chosenChar));
count[chosenChar]++;
}
// Sort replacements to ensure lexicographically smallest result
replacements.sort();
// Replace question marks
let result = '';
let replaceIndex = 0;
for (let i = 0; i < n; i++) {
if (s[i] === '?') {
result += replacements[replaceIndex++];
} else {
result += s[i];
}
}
return result;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n log 26) = O(n)，其中 n 是字符串长度。需要遍历字符串统计字符，对于每个问号进行堆操作，排序替换字符的时间为 O(k log k)，k 是问号数量，最坏情况下 k = n |
| 空间复杂度 | O(26 + k) = O(n)，需要存储 26 个字符的频次和待替换的字符列表 |