Solution: Smallest String With A Given Numeric Value

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1663 (Medium): Smallest String With A Given Numeric Value

---

Description:

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.

---

Examples:

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

---

Idea:

The basic idea is simple: in order for the string to be as lexigraphically "small" as it can be, you want to move as much of the "weight" towards the rear of the string as possible.

That means you want as many "z"s at the end of the answer and as many "a"s at the beginning of the answer as you can get. This also means that there will only be at most one character that is neither an "a" or a "z".

First, remove n from k in order to leave yourself "room" to fill the remaining space with "a"s when you're done. This is as if you're spending n value of k to initially fill each position with an "a". After that, each character will be considered by how much of an increase it is over "a", thus a "z" has a value of 25, because it's 25 "more" than an "a". That also coincidentally makes thing easier with a 0-indexed alphabet reference string.

Then start with as many "z"s as you can fit in k, and use any leftover k for the middle character. Then fill out the start of ans with "a"s.

---

C++ Code:

class Solution {
    public:
        string getSmallestString(int n, int k) {
            k -= n;
            string alpha = "_bcdefghijklmnopqrstuvwxy_";
            string ans = std::string(~~(k / 25), 'z');
            if (k % 25) {
                ans = alpha[k % 25] + ans;
            }
            return std::string(n - ans.size(), 'a') + ans;
        }
    };

---

Python Code:

class Solution(object):
    def getSmallestString(self, n, k):
        k -= n
        alpha = '_bcdefghijklmnopqrstuvwxy_'
        ans = 'z' * (k // 25)
        if k % 25:
            ans = alpha[k % 25] + ans
        return 'a' * (n - len(ans)) + ans

---

Javascript Code:

var getSmallestString = function(n, k) {
    k -= n
    let alpha ='_bcdefghijklmnopqrstuvwxy_',
        ans = 'z'.repeat(~~(k / 25))
    if (k % 25) ans = alpha[k % 25] + ans
    return ans.padStart(n, 'a')
};

Comments

[lionel-rowe]

Nice solutions! You don't need to hard code the alphabet - you can just grab the codepoint of each character and subtract the codepoint of 'a'.

JS:

const a = 'a'.codePointAt(0) // 97
String.fromCharCode(k % 25 + a)

Python:

a = ord('a') # 97
chr(k % 25 + a)

Not too sure about C++ as I don't know the language, but I know that in C the char type is already an integer type, so it may not even need any conversion at all.

[seanpgallivan]

Thanks for the input!

Indeed, some of my early answers to this problem used String.fromCharCode(97 + k % 25), but I found that defining the alphabet was actually more performant, at least using leetcode's timers.

Up until recently, I've been posting these solutions only on leetcode's forums, so my goal was to find the absolute most performant method given their testing methods. But since I've recently started aggregating my past solutions here, I've stripped out the references to leetcode times and plan from here on out to focus a bit more on strictly O(n) efficiency and readability and less on leetcode's often-capricious timers.