Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

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.
Copy the code

Note:

1 <= n <= 10^5
n <= k <= 26 * n
Copy the code

parsing

This question is a combination of dictionary order, string concatenation, greed and many other aspects of the comprehensive test of students’ ability to solve the problem, more interesting.

For lowercase letters, the definition starts at 1, so a is 1, B is 2, C is 3, and so on. The numeric value of a string consisting of lowercase alphabetic characters is defined as the sum of the numeric values of all its alphabetic characters. For example, the value of the string “Abe” is equal to 1 + 2 + 5 = 8.

Given the definition given above, given two integers n and k. Returns the lexicographical minimum string of length n and string value k. Dictionary order is basically trying to put the smaller letters first and the larger letters later.

This problem is actually using greedy ideas to solve the problem, we just according to the meaning of the question, try to put the small number of letters in the front, the large number of letters in the back. But we need to know that the value of k is fixed, so we can reverse our thinking and place alphabetic characters from back to front:

  • Result is an empty string traversed from n to 0 (excluding)
  • TMP =min(26, k- I +1) Append TMP to result (example 1, if we put z at the end, the second digit will be a, and the first digit will have no letter, which does not satisfy the condition of length N)
  • And then k minus TMP, and then do the following traversal, as shown above
  • At the end of the loop, because we place the letters from back to front, we can reverse result at the end.

The time complexity is O(N), and the space complexity is O(N).

answer

class Solution(object):
    def getSmallestString(self, n, k):
        result = ''
        for i in range(n, 0, -1):
            tmp = min(26, k-i+1)
            result += chr(ord('a') + tmp - 1)
            k -= tmp
        return result[::-1]
Copy the code

The results

Runtime: 1156 MS, faster than 61.54% of Python online submissions for A Given String With Numeric Value. Memory Usage: Given in Python online submissions for A Given Numeric Value.Copy the code

The original link

Leetcode.com/problems/sm…

Your support is my biggest motivation