Question

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

English Version

题目描述

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

解法

方法一：贪心

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

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

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

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)

class Solution {
  public String getSmallestString(int n, int k) {
    char[] ans = new char[n];
    Arrays.fill(ans, 'a');
    int i = n - 1, d = k - n;
    for (; d > 25; d -= 25) {
      ans[i--] = 'z';
    }
    ans[i] = (char) ('a' + d);
    return String.valueOf(ans);
  }
}

class Solution {
public:
  string getSmallestString(int n, int k) {
    string ans(n, 'a');
    int i = n - 1, d = k - n;
    for (; d > 25; d -= 25) {
      ans[i--] = 'z';
    }
    ans[i] += d;
    return ans;
  }
};

func getSmallestString(n int, k int) string {
  ans := make([]byte, n)
  for i := range ans {
    ans[i] = 'a'
  }
  i, d := n-1, k-n
  for ; d > 25; i, d = i-1, d-25 {
    ans[i] = 'z'
  }
  ans[i] += byte(d)
  return string(ans)
}