Solution: Smallest String With A Given Numeric Value
Tags: algorithms, javascript, leetcode
Published: 2021-02-03 04:57:41

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/smallest-string-with-a-given-numeric-value/discuss/1038789/c-python-javascript-o1-easy-solution-w-explanation-beats-100-100).*

---

####[Leetcode Problem #1663 (*Medium*): Smallest String With A Given Numeric Value](https://leetcode.com/problems/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,<br>and it is the smallest string with such a value<br>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:***
```c++
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:***
```python
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:***
```javascript
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')
};
```