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

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

• 思路：贪心

局部最优：在保证字符串长度一定，优先在字符串尾部插入数值最大的字符，即使首部字符串尽可能为a、尾部字符串尽可能为z

全局最优：字符串的字典顺序最小

• 实现【总体超时】

从尾部开始插入字符，当n和k一定时，前n−1个字符需要的分数最少为n−1，那么可供第n个字符使用的分数为k−(n−1)，因此第n个字符一定

。如果k−(n−1)>=26，那么尾部可以插入的最小字符为z='a'+25，贡献的分数为26

。如果k−(n−1)<26，那么尾部可以插入的最小字符为'a' + k-n，贡献的分数为k−n+1

class Solution {
    public String getSmallestString(int n, int k) {
        StringBuilder sb = new StringBuilder();      
        while (n > 0){
            if (k - n + 1 >= 26){
                sb.insert(0, (char)('a' + 25));
                k -= 26;
            }else{
                sb.insert(0, (char)('a' + k - n));
                k -= k - n + 1;
            }
            n--;
        }
        return sb.toString();
    }
}

。复杂度

• 时间复杂度：O ( n ² ) ，每构造一位字符需要将字符串后移一位，需要的时间复杂度为O(n)，因此总时间复杂度为O ( n ² )

• 空间复杂度：O ( 1 )

• 实现

从头部开始插入字符，当n 和k一定时，使前面的字符尽可能为a，后面的字符尽可能为z。当构造第i个字符时，后n−i个字符全为z需要的分数为(n−i)∗26，那么第i个字符需要贡献的分数为max(1,k−(n−i)∗26)

。如果k−(n−i)∗26>1，那么表示尾部全部插入z，仍有分数剩余，那么第i个字符应插入'a'+k-(n-i)*26-1，贡献的分数为k−(n−i)∗26

。如果k−(n−i)∗26<=1，那么表示尾部全部插入z，没有分数剩余甚至还有同于，那么第i个字符可以插入的最小字符'a'，贡献的分数为1

class Solution {
    public String getSmallestString(int n, int k) {
        StringBuilder sb = new StringBuilder();      
        while (n > 0){
            int lower = Math.max(1, k - (n - 1) * 26);
            sb.append((char)('a'+ lower - 1));
            k -= lower;
            n--;
        }
        return sb.toString();
    }
}

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( 1 )