How can I minimize the cost of the string in the 'Replace Question Marks in String to Minimize Its Value' problem?

To minimize the cost, replace '?' with the smallest lexicographical character while maintaining invariant validation to ensure previous characters don't repeat excessively.

What is the time complexity of solving the 'Replace Question Marks in String to Minimize Its Value' problem?

The time complexity depends on the approach but can be optimized to O(n) by using a hash table for frequency counting and greedy character selection.

What is the role of the hash table in solving the 'Replace Question Marks in String to Minimize Its Value' problem?

A hash table tracks the frequency of characters already in the string, allowing efficient character replacement and ensuring minimal cost without excessive repetition.

Can there be multiple valid solutions for this problem?

Yes, there can be multiple valid solutions with the same minimum cost. However, the lexicographically smallest solution is preferred.

What is the greedy approach used in the 'Replace Question Marks in String to Minimize Its Value' problem?

The greedy approach involves choosing the lexicographically smallest valid character to replace '?' in each step, ensuring the minimal cost at each stage of the string.

#3081

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

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

哈希表字符串贪心排序堆（优先队列）

题目描述

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

lightbulb

解题思路

方法一：贪心 + 优先队列

根据题目，我们可以发现，如果一个字母 $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$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate demonstrate understanding of greedy algorithms and their application to string problems?
question_mark
Is the candidate able to explain how the cost function influences their decision-making process?
question_mark
How effectively does the candidate use hash tables to minimize cost while ensuring lexicographical order?

warning

常见陷阱

外企场景

error
Misunderstanding the cost calculation and how previous characters influence the current cost.
error
Failing to consider the lexicographical order of the string while replacing '?' characters.
error
Overcomplicating the solution by not utilizing hash tables efficiently for counting character occurrences.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to handle a larger character set, such as including uppercase letters or digits.
arrow_right_alt
Introduce a limit on the number of distinct characters allowed in the string.
arrow_right_alt
Allow multiple valid outputs with the same cost but ask for the lexicographically largest string.

help

常见问题

外企场景

继续练习

#3085 成为 K 特殊字符串需要删除的最少字符数 #3035 回文字符串的最大数量 #3016 输入单词需要的最少按键次数 II