日28 -与えられた数値で最も小さいストリング

問題

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.

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

例2 :

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)

分析

解説

私の解決性能はすごい!私は標準的な文字列連結を試みました、しかし、それはさらに悪化しました.私がここでよりよくすることができるかわからない.私は学ぶべきことがたくさんある.私は、キューが拡張左ビットでストリングを構築するのが速いと思いました.
解決自体は簡単です.n -1からスタートし、帰り道を進め、可能な最大値をaに割り当てる.これをキューに追加します.最後にキューを文字列に変換します.アルファベットで26文字があるので、26は最大可能な価値です.私たちは本質的にZを切り刻んでいます.