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"

 

提示：

• 1 <= n <= 105
• n <= k <= 26 * n

解题思路

尝试在当前位置 \(i\) 依次放置 \(j, 1\le j \le 26\)，如果 \(k\gt j+26\times(n-i)<k\)，说明当前位置放置字母 \(chr(j+96)\) 后，之后的位置全部放置 \(z\)，字母之和也不可能达到 \(k\)；反之，则在当前位置放置字母 \(chr(j+96)\)。

---

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        ans = [""] * n
        for i in range(1, n + 1):
            for j in range(1, 27):
                if j + 26 * (n - i) >= k:
                    ans[i - 1] = chr(j + 96)
                    k -= j
                    break
        return "".join(ans)

---

测试数据

solution = Solution()

n = 3
k = 27
assert solution.getSmallestString(n, k) == "aay"

n = 5
k = 73
assert solution.getSmallestString(n, k) == "aaszz"

print("PASS!")

返回顶部

在手机上阅读