2022-03-22

Leetcode 1663 - Smallest String With A Given Numeric Value

Problem#

題目給你兩個數字 n 和 k 問你: 由 n 個字母組成，所有字母加起來總和為 k 且字串字典序最小。
a=1, b=2, …, z=26

想法#

最優的答案是後面都是 z 前面都是 a，先貪心找最後的 z 長度: 對於字串 Z = aa...z = 1*(a長度) + 26 假如 k 大於 Z 的話，則最後一定可以擺一個 z，亦即 k >= 1*(n-1) + 26。
接下來就都擺 a ，中間的字母(夾在 a 和 z 中間 e.g. “aa…x…zz”)，就擺 'a'+(k-1)

時間複雜度: $\mathcal{O}(n)$
空間複雜度: $\mathcal{O}(n)$

AC Code#

        Copy
        class Solution
    string getSmallestString(int n, int k)
        string fr, mi, ba;
        while(k >= 1*(n-1)+26)
            ba += 'z';
            n--;
        while(n > 1)
            fr += 'a';
            k--;
            n--;
        if(k > 0)
            mi += 'a' + (k-1);
        // cout << fr << mi << ba << '\n';
        return fr + mi + ba;

      

view raw 1663.cpp delivered with ❤ by emgithub

賞析#

先全部填 a 然後再從後頭處理 z`
- https://leetcode.com/problems/smallest-string-with-a-given-numeric-value/discuss/1871705/oror-C%2B%2Boror-Easy-Approach-oror-PROPER-EXPLANATION

	class Solution
	{
	public:
	string getSmallestString(int n, int k)
	{
	string fr, mi, ba;

	while(k >= 1*(n-1)+26)
	{
	ba += 'z';
	k -= 26;
	n--;
	}

	while(n > 1)
	{
	fr += 'a';
	k--;
	n--;
	}

	if(k > 0)
	mi += 'a' + (k-1);

	// cout << fr << mi << ba << '\n';

	return fr + mi + ba;
	}
	};