## DEV Community is a community of 890,178 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Ruairí O'Brien

Posted on

# Day 28 - Smallest String With A Given Numeric Value

## The Problem

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.

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)
``````

## 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.