## The Problem

The

numeric valueof alowercase characteris 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 valueof astringconsisting 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 thelexicographically smallest stringwithlengthequal to`n`

andnumeric valueequal 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`

## Tests

```
import pytest
from .Day28_SmallestStringWithAGivenNumericValue import Solution
s = Solution()
@pytest.mark.parametrize(
"n,k,expected",
[
(3, 27, "aay"),
(5, 73, "aaszz"),
],
)
def test_get_smallest_string(n, k, expected):
assert s.getSmallestString(n, k) == expected
```

## Solution

```
from collections import deque
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
d = deque()
i = n - 1
while i >= 0:
a = min(k - i, 26)
d.extendleft(chr(a + ord("a") - 1))
k -= a
i -= 1
return "".join(d)
```

## Analysis

## Commentary

My solution performance is terrible!!! I tried doing standard string concatenation but that performed even worse. Not sure what I can do better here. I have a lot to learn. I thought a queue would be quick for building the string with the extend left bit.

The solution itself is straightforward enough. Start from `n -1`

and work the way back and assign the maximum possible numeric value to `a`

. Prepend that to the queue. At the end convert the queue to a string. `26`

is the max possible value since there's 26 letters in the alphabet. We're essentially chopping up z as we go to fit it into n pieces.

## Top comments (0)