Question

1663. Smallest String With A Given Numeric Value

中文文档

Description

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

Solutions

Solution 1: Greedy

First, we initialize each character of the string to 'a', leaving a remaining value of $d=k-n$.

Then, we traverse the string from back to front. In each iteration, we greedily replace the current character with the character 'z' that can minimize the remaining number, until the remaining number does not exceed $25$. Finally, we add the remaining number to the position we have traversed.

The time complexity is $O(n)$, where $n$ is the length of the string. Ignoring the space consumption of the answer, the space complexity is $O(1)$.

class Solution:
  def getSmallestString(self, n: int, k: int) -> str:
    ans = ['a'] * n
    i, d = n - 1, k - n
    while d > 25:
      ans[i] = 'z'
      d -= 25
      i -= 1
    ans[i] = chr(ord(ans[i]) + d)
    return ''.join(ans)

class Solution {
  public String getSmallestString(int n, int k) {
    char[] ans = new char[n];
    Arrays.fill(ans, 'a');
    int i = n - 1, d = k - n;
    for (; d > 25; d -= 25) {
      ans[i--] = 'z';
    }
    ans[i] = (char) ('a' + d);
    return String.valueOf(ans);
  }
}

class Solution {
public:
  string getSmallestString(int n, int k) {
    string ans(n, 'a');
    int i = n - 1, d = k - n;
    for (; d > 25; d -= 25) {
      ans[i--] = 'z';
    }
    ans[i] += d;
    return ans;
  }
};

func getSmallestString(n int, k int) string {
  ans := make([]byte, n)
  for i := range ans {
    ans[i] = 'a'
  }
  i, d := n-1, k-n
  for ; d > 25; i, d = i-1, d-25 {
    ans[i] = 'z'
  }
  ans[i] += byte(d)
  return string(ans)
}