{"id":7699,"date":"2020-11-22T14:33:02","date_gmt":"2020-11-22T22:33:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7699"},"modified":"2020-11-22T14:35:07","modified_gmt":"2020-11-22T22:35:07","slug":"leetcode-1663-smallest-string-with-a-given-numeric-value","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1663-smallest-string-with-a-given-numeric-value\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1663. Smallest String With A Given Numeric Value"},"content":{"rendered":"\n

The numeric value<\/strong> of a lowercase character<\/strong> is defined as its position (1-indexed)<\/code> in the alphabet, so the numeric value of a<\/code> is 1<\/code>, the numeric value of b<\/code> is 2<\/code>, the numeric value of c<\/code> is 3<\/code>, and so on.<\/p>\n\n\n\n

The numeric value<\/strong> of a string<\/strong> consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string \"abe\"<\/code> is equal to 1 + 2 + 5 = 8<\/code>.<\/p>\n\n\n\n

You are given two integers n<\/code> and k<\/code>. Return the lexicographically smallest string<\/strong> with length<\/strong> equal to n<\/code> and numeric value<\/strong> equal to k<\/code>.<\/em><\/p>\n\n\n\n

Note that a string x<\/code> is lexicographically smaller than string y<\/code> if x<\/code> comes before y<\/code> in dictionary order, that is, either x<\/code> is a prefix of y<\/code>, or if i<\/code> is the first position such that x[i] != y[i]<\/code>, then x[i]<\/code> comes before y[i]<\/code> in alphabetic order.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> n = 3, k = 27\nOutput:<\/strong> \"aay\"\nExplanation:<\/strong> 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.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 5, k = 73\nOutput:<\/strong> \"aaszz\"\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= n <= 105<\/sup><\/code><\/li>
  • n <= k <= 26 * n<\/code><\/li><\/ul>\n\n\n\n
    Solution: Greedy, Fill in reverse order<\/strong><\/h2>\n\n\n\n
    Fill the entire string with ‘a’, k-=n, then fill in reverse order, replace ‘a’ with ‘z’ until not enough k left.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\nclass Solution {\npublic:\n  string getSmallestString(int n, int k) {    \n    string ans(n, 'a');\n    k -= n;\n    while (k) {\n      int d = min(k, 25);\n      ans[--n] += d;\n      k -= d;\n    }\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def getSmallestString(self, n: int, k: int) -> str:\n    ans = ['a'] * n\n    k -= n\n    i = n - 1\n    while k:\n      d = min(k, 25)\n      ans[i] = chr(ord(ans[i]) + d)\n      k -= d\n      i -= 1\n    return ''.join(ans)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,4],"class_list":["post-7699","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7699","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7699"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7699\/revisions"}],"predecessor-version":[{"id":7701,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7699\/revisions\/7701"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7699"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7699"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7699"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}