What is the greedy approach in the Lexicographically Smallest String problem?

The greedy approach involves starting with the leftmost character and trying to change it to 'a', ensuring the total distance remains within the allowed k operations.

How do I calculate the distance between two strings?

The distance between two strings of the same length is the sum of the absolute differences of their corresponding characters' ASCII values.

What should I do when k equals zero?

If k equals zero, no changes can be made to the string, so the input string should be returned unchanged.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, as we iterate through the string once.

Can I use a dynamic programming approach for this problem?

A dynamic programming approach is not necessary for this problem, as a greedy strategy with careful validation is more efficient.

#3106

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

满足距离约束且字典序最小的字符串

给你一个字符串 s 和一个整数 k 。定义函数 distance(s 1 , s 2 ) ，用于衡量两个长度为 n 的字符串 s 1 和 s 2 之间的距离，即：字符 'a' 到 'z' 按循环顺序排列，对于区间 [0, n - 1] 中的 i ，计算所有「 s 1 [i] 和 s 2 [i…

字符串贪心

题目描述

给你一个字符串 s 和一个整数 k 。

定义函数 distance(s₁, s₂) ，用于衡量两个长度为 n 的字符串 s₁ 和 s₂ 之间的距离，即：

字符 'a' 到 'z' 按循环顺序排列，对于区间 [0, n - 1] 中的 i ，计算所有「 s₁[i] 和 s₂[i] 之间 最小距离」的和。

例如，distance("ab", "cd") == 4 ，且 distance("a", "z") == 1 。

你可以对字符串 s 执行 任意次 操作。在每次操作中，可以将 s 中的一个字母改变为任意其他小写英文字母。

返回一个字符串，表示在执行一些操作后你可以得到的 字典序最小 的字符串 t ，且满足 distance(s, t) <= k 。

示例 1：

输入：s = "zbbz", k = 3
输出："aaaz"
解释：在这个例子中，可以执行以下操作：
将 s[0] 改为 'a' ，s 变为 "abbz" 。
将 s[1] 改为 'a' ，s 变为 "aabz" 。
将 s[2] 改为 'a' ，s 变为 "aaaz" 。
"zbbz" 和 "aaaz" 之间的距离等于 k = 3 。
可以证明 "aaaz" 是在任意次操作后能够得到的字典序最小的字符串。
因此，答案是 "aaaz" 。

示例 2：

输入：s = "xaxcd", k = 4
输出："aawcd"
解释：在这个例子中，可以执行以下操作：
将 s[0] 改为 'a' ，s 变为 "aaxcd" 。
将 s[2] 改为 'w' ，s 变为 "aawcd" 。
"xaxcd" 和 "aawcd" 之间的距离等于 k = 4 。
可以证明 "aawcd" 是在任意次操作后能够得到的字典序最小的字符串。
因此，答案是 "aawcd" 。

示例 3：

输入：s = "lol", k = 0
输出："lol"
解释：在这个例子中，k = 0，更改任何字符都会使得距离大于 0 。
因此，答案是 "lol" 。

提示：

1 <= s.length <= 100
0 <= k <= 2000
s 只包含小写英文字母。

lightbulb

解题思路

方法一：枚举

我们可以遍历字符串 $s$ 的每个位置，对于每个位置，我们枚举所有小于当前字符的字符，计算改变到这个字符的代价 $d$ ，如果 $d \leq k$ ，我们就将当前位置的字符改为这个字符，并将 $k$ 减去 $d$ ，然后结束枚举，继续遍历下一个位置。

遍历结束后，我们就得到了一个满足条件的字符串。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        cs = list(s)
        for i, c1 in enumerate(s):
            for c2 in ascii_lowercase:
                if c2 >= c1:
                    break
                d = min(ord(c1) - ord(c2), 26 - ord(c1) + ord(c2))
                if d <= k:
                    cs[i] = c2
                    k -= d
                    break
        return "".join(cs)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The problem can be solved greedily with careful validation of the operations.
question_mark
Watch for edge cases like when k equals zero, where no operations can be performed.
question_mark
Candidates should be able to explain the trade-off of minimizing the string while adhering to the distance constraint.

warning

常见陷阱

外企场景

error
Not handling the case where k equals zero and no changes can be made.
error
Misunderstanding the distance calculation or failing to properly track the allowed distance.
error
Not considering the edge case where the string is already the lexicographically smallest, requiring no operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the operations are unlimited? This would simplify the problem significantly.
arrow_right_alt
Consider modifying the string to a fixed target rather than minimizing it.
arrow_right_alt
What if we were allowed to change only specific positions in the string rather than all characters?

help

常见问题

外企场景

继续练习

#3085 成为 K 特殊字符串需要删除的最少字符数 #3081 替换字符串中的问号使分数最小 #3170 删除星号以后字典序最小的字符串