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"

方法（贪心算法）

假设当前来到了一个位置，要往这个位置放一个字符。包括这个位置在内还需要放n’个位置，这些位置的和为k’

放完这个位置后，剩余还有n’-1个位置，这些位置的和最大值为26(n’-1),最小值为n’-1。分别为全为z和全为a的情况。因此，只有满足：n’ - 1 <= k’ - c <= 26 * (n’ - 1) 时，我们才能往这个位置放字符c。即：c需要满足：k’ - 26(n’ - 1) <= c <= k’ - (n’ - 1)

我们的贪心策略总是希望放一个尽可能小的字符，因此我们就放c的下限：k’ - 26(n’ - 1)。如果这个下限小于0，我们就放a。否则，我们放这个下限对应的字符

代码

public static String getSmallestString(int n, int k) {
    StringBuilder str = new StringBuilder();
    while(n > 0){
        int bound = k - 26 * (n - 1);
        if(bound > 0) {
            str.append((char) (bound + 'a' - 1));
            k -= bound;
        }
        else{
            str.append('a');
            k -= 1;
        }
        n--;
    }
    return str.toString();
}