Skip to content

LeetCode: 1663-Smallest String With A Given Numeric Value 解題紀錄

Last Updated on 2022-03-24 by Clay

題目

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.

Example 1:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

Example 2:

Input: n = 5, k = 73
Output: "aaszz"

Constraints:

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

題目僅會輸入兩個數字 n 以及 k，其中 n 代表最終回傳的字串長度，k 代表字串中的字母數值加總的總值（a=1 ... z=26），而我們要回傳的字串乍看之下有很多種可能，但僅需回傳字典序最小的字串即可。

比方說 aab 和 aba 總值皆為 4，但應該回傳字典序比較小的 aab。

解題思路

Greedy 解法

由於是要返回最小的字典序字串，故其實可以使用貪婪解的方法去求出答案。

（註：所謂的字典序就是 aab 和 aba 雖然都是同樣的字元組成，但前者比後者小）

比方說，一開始假設字串中所有的的字母都是 a，這樣我們當前值剛好為返回字串的長度、亦即為 n，接著我們再去計算與目標值 k 之間的差距；按照貪婪解法，我們嘗試從最後一個字元開始置換成 z，並將當前值加上 25（原本的 a 為 1 而 z 為 26，是故增加 25）...... 如果當前值跟 k 之間的差距不足 25，則剛好填入相差數字所代表的字母。

以 Example 2 來做範例，n = 5, k = 73：

s="aaaaa", val=5
s="aaaaz", val=30
s="aaazz", val=55 （注意，這邊跟所求的 k 值僅相差 18，填入對應的數字 19 即可 –– 因為需要替換掉一個 a）
s="aaszz", val=73 <= 答案！


Greedy 解法複雜度

Time complexityO(n)
Space complexityO(n)


Greedy 解法 C++ 範例程式碼

class Solution {
public:
    string getSmallestString(int n, int k) {
        // Init
        string s(n, 'a');
        int i = s.size() - 1;
        
        // Distance
        k -= n;
        
        // Matching the target string
        while (k != 0) {
            if (k > 25) {
                s[i] = 'z';
                k -= 25;
            }
            else {
                s[i] = k + 'a';
                k = 0;
            }
                        
            --i;
        }
        
        return s;
    }
};



Greedy 解法 Python 範例程式碼

class Solution {
public:
    string getSmallestString(int n, int k) {
        // Init
        string s(n, 'a');
        int i = s.size() - 1;
        
        // Distance
        k -= n;
        
        // Matching the target string
        while (k != 0) {
            if (k > 25) {
                s[i] = 'z';
                k -= 25;
            }
            else {
                s[i] = k + 'a';
                k = 0;
            }
                        
            --i;
        }
        
        return s;
    }
};

References

Read More

Tags:

Leave a Reply