[LC Walkthrough] 1663. Smallest String With A Given Numeric Value

Hello world! This is the very first article of LeetCode Walkthrough where I record my thinking process to the solution to LeetCode problems.

I decided to write about 1663. Smallest String With A given Numeric Value as it was the most recent problem I worked on.

For this problem, we need to come up with the lexicographically smallest string with length equal to n and numeric value equal to k.

The definition required to solve this problem is explained well in the problem statement, so I recommend you to take a look if you are confused with all these new lingos.

The first thought that came to my mind is that we would want to put bigger alphabets to the end of the string since we want the lexicographically smallest string; the string will have bigger lexicographical value if bigger alphabets is at the front.

Consider the case where n = 3 and k = 27:

We would want “aay” instead of “yaa” here, since “yaa” is lexicographically bigger than “ayy”.

Therefore, I decided to take an approach where we start from the end and greedily put the biggest alphabet. However, we can’t just easily take the biggest possible alphabet at a certain index.

Again, consider the case where n = 3 and k = 27:

We won’t have any k-value left at index 0

If we simply just put the biggest available alphabet, we will eventually run out of k-value at some point. Hence, when we decide which alphabet to put, we will also have to be considerate of the count of letters left. Surprisingly, the letters left at a certain index can be easily calculated; it is actually the value of index itself (assuming the index is 0-based).

At index 2, we will have 2 letters left to fill and so on

With these factors in mind, we can come up with the following solution:

getNthAlphabet(int n) is a helper method to get n-th alphabet (1-based index)

Let us run a simple test case where n = 3 and k = 27:

The time complexity of this solution is O(n) where n = length of string. The while-loop gets executed n-times to create the new string.

The space complexity of this solution is O(n) where n = length of string. The creation of new string (String.valueOf(res)) takes n amount of space.

Since I solve at least one problem a day during weekdays, I’ll try to post these walkthroughs daily. Until then, stay tuned. Thanks for reading!