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)

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.