10.3 字符串贪心

约 5627 字大约 19 分钟

2025-05-26

10.3.1 字典序最小/最大

字典序的定义如下：

对于两个字符串 a 和 b，从左到右依次比较 a[i] 和 b[i] 的字符 ASCII 值的大小。
a[i]!=b[i] 时，如果 a[i]<b[i]，那么 a 的字典序更小，否则 b 的字典序更小。
如果没有出现 a[i]!=b[i]，则短的字符串字典序更小。
如果两个字符串的长度和内容均相同，那么两个字符串的字典序一样。

字典序的定义也可以推广到数组上，按照上述方法比较两个数组的字典序。

1323. 6 和 9 组成的最大数字
给你一个仅由数字 6 和 9 组成的正整数 num。你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。请返回你可以得到的最大数字。
示例 1：
输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。
示例 2：
输入：num = 9996
输出：9999
解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。
示例 3：
输入：num = 9999
输出：9999
解释：无需改变就已经是最大的数字了。
提示
思路：转换成字符串调用 replace 函数即可。
```
class Solution:
def maximum69Number (self, num: int) -> int:
    return int(str(num).replace('6', '9', 1))
```
时间复杂度： $O(n)$ ，其中 n 为 num 的长度。
空间复杂度： $O(n)$ 。
3216. 交换后字典序最小的字符串
给你一个仅由数字组成的字符串 s，在最多交换一次相邻且具有相同奇偶性的数字后，返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。
示例 1：
输入： s = "45320"
输出： "43520"
解释：
s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。
示例 2：
输入： s = "001"
输出： "001"
解释：
无需进行交换，因为 s 已经是字典序最小的。
提示
思路：从第二个数字开始遍历，如果比上一个数字小，且这两个数字奇偶性相同（相加为偶数），则交换位置，最后返回交换后的字符串。
```
class Solution:
def getSmallestString(self, s: str) -> str:
    l = list(s)
    for i in range(1, len(l)):
        if l[i - 1] > l[i] and (int(l[i - 1]) + int(l[i])) % 2 == 0:
            l[i - 1], l[i] = l[i], l[i - 1]
            break
    return ''.join(l)
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
2697. 字典序最小回文串
给你一个由小写英文字母组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母替换 s 中的一个字符。请你执行尽可能少的操作，使 s 变成一个回文串。如果执行最少操作次数的方案不止一种，则只需选取字典序最小的方案。对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。返回最终的回文字符串。
示例 1：
输入：s = "egcfe"
输出："efcfe"
解释：将 "egcfe" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需将 'g' 改为 'f' 。
示例 2：
输入：s = "abcd"
输出："abba"
解释：将 "abcd" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 "abba" 。
示例 3：
输入：s = "seven"
输出："neven"
解释：将 "seven" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "neven" 。
提示
思路：使用两个指针，分别从前后开始往中间遍历，如果不相同则将字典序大的替换。
```
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
    l = list(s)
    left = 0
    right = len(l) - 1
    while left < right:
        if l[left] > l[right]:
            l[left] = l[right] 
        else:
            l[right] = l[left]
        left += 1
        right -= 1
    return ''.join(l)
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
1881. 插入后的最大值
给你一个非常大的整数 n 和一个整数数字 x ，大整数 n 用一个字符串表示。n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中，且 n 可能表示一个负数。你打算通过在 n 的十进制表示的任意位置插入 x 来最大化 n 的数值。但不能在负号的左边插入 x 。例如，如果 n = 73 且 x = 6 ，那么最佳方案是将 6 插入 7 和 3 之间，使 n = 763 。如果 n = -55 且 x = 2 ，那么最佳方案是将 2 插在第一个 5 之前，使 n = -255 。返回插入操作后，用字符串表示的 n 的最大值。
示例 1：
输入：n = "99", x = 9
输出："999"
解释：不管在哪里插入 9 ，结果都是相同的。
示例 2：
输入：n = "-13", x = 2
输出："-123"
解释：向 n 中插入 x 可以得到 -213、-123 或者 -132 ，三者中最大的是 -123 。
提示
思路：对于正数，要求找到第一个严格小于x的数，插在这个数前面；对于负数，找到第一个严格大于x的数，插在这个数前面；如果没找到，插在最后。
```
class Solution:
def maxValue(self, n: str, x: int) -> str:
    l = list(n)
    if l[0] == '-':
        for i in range(1, len(l)):
            if int(l[i]) > x:
                l.insert(i, str(x))
                break
            if i == len(l) - 1:
                l.append(str(x))
    else:
        for i in range(len(l)):
            if int(l[i]) < x:
                l.insert(i, str(x))
                break
            if i == len(l) - 1:
                l.append(str(x))
    return ''.join(l)
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
2734. 执行子串操作后的字典序最小字符串
给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。返回执行上述操作恰好一次后可以获得的字典序最小的字符串。子字符串是字符串中的一个连续字符序列。现有长度相同的两个字符串 x 和字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小。
示例 1：
输入：s = "cbabc"
输出："baabc"
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。
示例 2：
输入：s = "acbbc"
输出："abaab"
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。
示例 3：
输入：s = "leetcode"
输出："kddsbncd"
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。
提示
思路：从左起第一个不为a的字符开始替换，直到遇到a，这题比较坑的是aa也需要换成az，我使用了一个change变量记录是否改变，如果没有改变，那么把最后一个a改成z。
```
class Solution:
def smallestString(self, s: str) -> str:
    l = list(s)
    change = False
    for i in range(len(l)):
        if l[i] != 'a':
            l[i] = chr(ord(l[i]) - 1)
            change = True
        else:
            if i == len(l) - 1 and not change:
                l[i] = 'z'
            if i != 0 and change:
                break
    return ''.join(l)
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
1946. 子字符串突变后可能得到的最大整数
给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且下标从 0 开始的整数数组 change ，该数组将 0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。你可以选择突变 num 的任一子字符串。突变子字符串意味着将每位数字 num[i] 替换为该数字在 change 中的映射（也就是说，将 num[i] 替换为 change[num[i]]）。请你找出在对 num 的任一子字符串执行突变操作（也可以不执行）后，可能得到的最大整数，并用字符串表示返回。子字符串是字符串中的一个连续序列。
示例 1：
输入：num = "132", change = [9,8,5,0,3,6,4,2,6,8]
输出："832"
解释：替换子字符串 "1"：
- 1 映射为 change[1] = 8 。
  因此 "132" 变为 "832" 。
  "832" 是可以构造的最大整数，所以返回它的字符串表示。
示例 2：
输入：num = "021", change = [9,4,3,5,7,2,1,9,0,6]
输出："934"
解释：替换子字符串 "021"：
- 0 映射为 change[0] = 9 。
- 2 映射为 change[2] = 3 。
- 1 映射为 change[1] = 4 。
  因此，"021" 变为 "934" 。
  "934" 是可以构造的最大整数，所以返回它的字符串表示。
示例 3：
输入：num = "5", change = [1,4,7,5,3,2,5,6,9,4]
输出："5"
解释："5" 已经是可以构造的最大整数，所以返回它的字符串表示。
提示
思路：从左起如果改了会变小并且还没有发生改变，就保留这次机会，遍历下一个，如果改变会变大，那么从这里开始改变，changed变为True，如果遇到变小的同时开始改变了，那么结束。
```
class Solution:
def maximumNumber(self, num: str, change: List[int]) -> str:
    l = list(num)
    changed = False
    for i in range(len(l)): # O(n)
        if change[int(l[i])] <= int(l[i]) and not changed:
            continue
        if change[int(l[i])] >= int(l[i]):
            l[i] = str(change[int(l[i])])
            changed = True
        elif changed:
            break
    return ''.join(l)
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
3517. 最小回文排列 I
给你一个回文字符串 s。返回 s 的按字典序排列的最小回文排列。如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个回文字符串。排列是字符串中所有字符的重排。如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。
示例 1：
输入： s = "z"
输出： "z"
解释：
仅由一个字符组成的字符串已经是按字典序最小的回文。
示例 2：
输入： s = "babab"
输出： "abbba"
解释：
通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。
示例 3：
输入： s = "daccad"
输出： "acddca"
解释：
通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。
提示
思路：给定的是回文串，那么可以只看前半部分，排序即可，再拼接上反转的前部分，最后判断是否要插入最中间的值。
```
class Solution:
def smallestPalindrome(self, s: str) -> str:
    temp = sorted(s[:len(s) // 2])
    res = []
    res.extend(temp)
    temp.reverse()
    res.extend(temp)
    if len(s) % 2 == 1:
        res.insert(len(s) // 2, s[len(s) // 2])
    return ''.join(res)
```
时间复杂度： $O(nlogn)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
1663. 具有给定数值的最小字符串
小写字符的数值是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。字符串由若干小写字符组成，字符串的数值为各字符的数值之和。例如，字符串 'abe' 的数值等于 1 + 2 + 5 = 8 。给你两个整数 n 和 k 。返回长度等于 n 且数值等于 k 的字典序最小的字符串。注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：x 是 y 的一个前缀；如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。
示例 1：
输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。
示例 2：
输入：n = 5, k = 73
输出："aaszz"
提示
思路：前面要尽可能地小，接近a，那么反过来，后面要尽可能地大，接近z；我们可以先初始化n个a，然后从后往前把每个位置加到z，直到用完k为止。
```
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
    l = ['a'] * n
    k -= n
    for i in range(len(l) - 1, -1, -1):
        if k >= 25:
            k -= 25
            l[i] = 'z'
        else:
            l[i] = chr(ord(l[i]) + k)
            break
    return ''.join(l)
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
1328. 破坏回文串
给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中一个字符用任意小写英文字母替换，使得结果字符串的字典序最小，且不是回文串。请你返回结果字符串。如果无法做到，则返回一个空串。如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，'abcc' 字典序比 'abcd' 小，因为不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。
示例 1：
输入：palindrome = "abccba"
输出："aaccba"
解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
在所有方法中，"aaccba" 的字典序最小。
示例 2：
输入：palindrome = "a"
输出：""
解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。
提示
思路：如果长度为一，那么一定是回文串，返回空串；接下来遍历前半部分，如果遇到不是 'a' 的字符，直接替换为 'a' ，如果全是 'a' ，那么把最后一个 'a' 换成 'b' 。
```
class Solution:
def breakPalindrome(self, palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
        return ''
    for i in range(n // 2): # O(n)
        if palindrome[i] != 'a':
            return palindrome[:i] + 'a' + palindrome[i + 1:]
    return palindrome[:-1] + 'b'
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
2259. 移除指定数字得到的最大结果
给你一个表示某个正整数的字符串 number 和一个字符 digit 。从 number 中恰好移除一个等于 digit 的字符后，找出并返回按十进制表示最大的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。
示例 1：
输入：number = "123", digit = "3"
输出："12"
解释："123" 中只有一个 '3' ，在移除 '3' 之后，结果为 "12" 。
示例 2：
输入：number = "1231", digit = "1"
输出："231"
解释：可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。
由于 231 > 123 ，返回 "231" 。
示例 3：
输入：number = "551", digit = "5"
输出："51"
解释：可以从 "551" 中移除第一个或者第二个 '5' 。
两种方案的结果都是 "51" 。
提示
思路：暴力，遇到相等的地方就提取出来当前值，最后取一个最大值。
```
class Solution:
def removeDigit(self, number: str, digit: str) -> str:
    return max(number[:i] + number[i + 1:] for i, c in enumerate(number) if c == digit)
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
2566. 替换一个数字后的最大差值
给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字替换成另一个数字。请你返回将 num 中恰好一个数字进行替换后，得到的最大值和最小值的差为多少。注意：当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。替换后得到的数字可以包含前导 0 。Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。
示例 1：
输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。
示例 2：
输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。
提示
思路：转化为字符串，从左往右遍历第一个不是 9 的数字，把这个数字全部替换为 9 得到最大值，然后因为第一位一定不是 0 ，因此直接替换和第一位相同的所有数字为 0 ，得到最小值，相减即可。
```
class Solution:
def minMaxDifference(self, num: int) -> int:
    s = str(num)
    max_s = num
    for i, ch in enumerate(s):
        if int(ch) < 9:
            max_s = int(s.replace(ch, '9'))
            break
    return max_s - int(s.replace(s[0], '0'))
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。

10.3.2 回文串贪心

409. 最长回文串
给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的最长的回文串的长度。在构造过程中，请注意区分大小写。比如 'Aa' 不能当做一个回文字符串。
示例 1：
输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2：
输入:s = "a"
输出:1
解释：可以构造的最长回文串是"a"，它的长度是 1。
提示
思路：先用一个计数器统计每个元素出现的次数，然后去处理次数，如果是偶数直接加上，如果是奇数，那么加上再减一，最后如果并不是所有字符都用上了，可以在正中间插入一个。
```
class Solution:
def longestPalindrome(self, s: str) -> int:
    from collections import Counter
    cnt = Counter(s)
    res = 0
    for num in cnt.values():
        res +=  num - num % 2
    return res + 1 if len(s) != res else res
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
2697. 字典序最小回文串
给你一个由小写英文字母组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母替换 s 中的一个字符。请你执行尽可能少的操作，使 s 变成一个回文串。如果执行最少操作次数的方案不止一种，则只需选取字典序最小的方案。对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。返回最终的回文字符串。
示例 1：
输入：s = "egcfe"
输出："efcfe"
解释：将 "egcfe" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需将 'g' 改为 'f' 。
示例 2：
输入：s = "abcd"
输出："abba"
解释：将 "abcd" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 "abba" 。
示例 3：
输入：s = "seven"
输出："neven"
解释：将 "seven" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "neven" 。
提示
思路：做过的。
```
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
    l = list(s)
    left = 0
    right = len(l) - 1
    while left < right:
        if l[left] > l[right]:
            l[left] = l[right] 
        else:
            l[right] = l[left]
        left += 1
        right -= 1
    return ''.join(l)
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
680. 验证回文串 II
给你一个字符串 s，最多可以从中删除一个字符。请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
示例 1：
输入：s = "aba"
输出：true
示例 2：
输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。
示例 3：
输入：s = "abc"
输出：false
提示
思路：使用两个指针从首尾往中间遍历，如果遇到不一样的地方，则尝试分别删除左边和右边。
```
class Solution:
def validPalindrome(self, s: str) -> bool:
    left = 0
    right = len(s) - 1

    def fun(s):
        return s == s[::-1]

    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
            continue
        return fun(s[left + 1: right + 1]) or fun(s[left: right])
    return True
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。
提示
可以使用 s == s[::-1] 来判断一个字符串是不是回文串。