What is the pattern used in 'Smallest String With A Given Numeric Value'?

The pattern is greedy choice with invariant validation. You make greedy choices at each step while ensuring the remaining sum can still be achieved by future characters.

What happens if k is too large for the string length?

If k exceeds the possible maximum sum (26 * n), it's impossible to achieve the target sum, and the problem is unsolvable.

Can the string contain characters other than lowercase letters?

No, the string is restricted to lowercase alphabetic characters, where 'a' has a numeric value of 1 and 'z' has a numeric value of 26.

How can I optimize this solution for large inputs?

To optimize, iterate from left to right, adjusting characters greedily, and ensure you don't exceed the required sum. The time complexity is O(n), so it's already efficient.

What is the best strategy to handle edge cases in this problem?

Ensure that you check for both small and large values of n and k. Handle cases where k is very close to the maximum sum possible for the given string length.

#1663

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

具有给定数值的最小字符串

小写字符的数值是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ， b 的数值为 2 ， c 的数值为 3 ，以此类推。字符串由若干小写字符组成，字符串的数值为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。给你两个整数 n 和 k 。…

字符串贪心

题目描述

小写字符 的数值是它在字母表中的位置（从 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"

提示：

1 <= n <= 10⁵
n <= k <= 26 * n

lightbulb

解题思路

方法一：贪心

我们先将字符串的每个字符都初始化为 'a'，此时剩余的数值为 $d=k-n$ 。

接着从后往前遍历字符串，每次贪心地将当前位置的字符替换为能够使得剩余的数字最小的字符 'z'，直到剩余的数字不超过 $25$ 。最后将剩余的数字加到我们遍历到的位置上即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串的长度。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        ans = ['a'] * n
        i, d = n - 1, k - n
        while d > 25:
            ans[i] = 'z'
            d -= 25
            i -= 1
        ans[i] = chr(ord(ans[i]) + d)
        return ''.join(ans)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of greedy algorithms.
question_mark
The candidate can apply greedy choices within the constraints of the problem.
question_mark
The candidate addresses edge cases and can explain the invariant validation process.

warning

常见陷阱

外企场景

error
Failing to account for the remaining sum after each greedy step.
error
Not considering the possibility of overshooting the required sum when selecting the largest valid character.
error
Misunderstanding the lexicographical order when adjusting the string’s characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimize the string length while still achieving a numeric sum equal to k.
arrow_right_alt
Extend the problem to handle uppercase letters as well.
arrow_right_alt
Solve the problem for multiple queries simultaneously, optimizing for performance.

help

常见问题

外企场景

继续练习

#1647 字符频次唯一的最小删除次数 #1689 十-二进制数的最少数目 #1702 修改后的最大二进制字符串