smallest-string-with-a-given-numeric-value

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters&#39; numeric values. For example, the numeric value of the string <code>&quot;abe&quot;</code> is equal to <code>1 + 2 + 5 = 8</code>.

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

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

&nbsp;
Example 1:

<pre>
Input: n = 3, k = 27
Output: &quot;aay&quot;
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.
</pre>

Example 2:

<pre>
Input: n = 5, k = 73
Output: &quot;aaszz&quot;
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>n &lt;= k &lt;= 26 * n</code></li>
</ul>

getSmallestString

Smallest String With A Given Numeric Value

Greedy

String

小写字符 的 数值 是它在字母表中的位置（从 <code>1</code> 开始），因此 <code>a</code> 的数值为 <code>1</code> ，<code>b</code> 的数值为 <code>2</code> ，<code>c</code> 的数值为 <code>3</code> ，以此类推。

字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 <code>"abe"</code> 的数值等于 <code>1 + 2 + 5 = 8</code> 。

给你两个整数 <code>n</code> 和 <code>k</code> 。返回 长度 等于 <code>n</code> 且 数值 等于 <code>k</code> 的 字典序最小 的字符串。

注意，如果字符串 <code>x</code> 在字典排序中位于 <code>y</code> 之前，就认为 <code>x</code> 字典序比 <code>y</code> 小，有以下两种情况：

<ul>
	<li><code>x</code> 是 <code>y</code> 的一个前缀；</li>
	<li>如果 <code>i</code> 是 <code>x[i] != y[i]</code> 的第一个位置，且 <code>x[i]</code> 在字母表中的位置比 <code>y[i]</code> 靠前。</li>
</ul>

 

示例 1：

<pre>
输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。</pre>

示例 2：

<pre>
输入：n = 5, k = 73
输出："aaszz"
</pre>

 

提示：

<ul>
	<li><code>1 <= n <= 105</code></li>
	<li><code>n <= k <= 26 * n</code></li>
</ul>