The numeric value of a lowercase character is defined as its position
(1-indexed)in the alphabet, so the numeric value of
1, the numeric value of
2, the numeric value of
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
k. Return the lexicographically smallest string with length equal to
nand numeric value equal to
Note that a string
xis lexicographically smaller than string
yin dictionary order, that is, either
xis a prefix of
y, or if
Iis the first position such that
x[i] != y[I], then
y[I]in alphabetic order.
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.
Input: n = 5, k = 73 Output: "aaszz"
1 <= n <= 105
n <= k <= 26 * n
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
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)
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.