1663.SmallestStringWithAGivenNumericValue.py

'''
    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:
    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:
    Input: n = 5, k = 73
    Output: "aaszz"

    Constraints:
        - 1 <= n <= 10^5
        - n <= k <= 26 * n
'''
#Difficulty: Medium
#93 / 93 test cases passed.
#Runtime: 708 ms
#Memory Usage: 16 MB

#Runtime: 708 ms, faster than 49.41% of Python3 online submissions for Smallest String With A Given Numeric Value.
#Memory Usage: 16 MB, less than 40.66% of Python3 online submissions for Smallest String With A Given Numeric Value.

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        s = ''
        while n:
            if k - n >= 26:
                s += 'z'
                k -= 26
                n -= 1
            else:
                s += chr(k-n + 97)
                n -= 1
                k -= k - n
        return s[::-1]