Smallest String With A Given Numeric Value

Medium
1222.

Smallest String With A Given Numeric Value

Smallest String With A Given Numeric Value is a medium coding problem on strings and greedy, asked in Amazon and Microsoft interviews.

The numeric value of a lowercase letter is its position in the alphabet (a = 1, b = 2, …, z = 26), and the numeric value of a string is the sum of the values of its letters — for example "abe" has value 1 + 2 + 5 = 8.

Given integers n and k, return the lexicographically smallest string of length n whose numeric value is exactly k.

Example 1

Input
n = 4, k = 30
Output
aabz
Explanation
1 + 1 + 2 + 26 = 30.

Example 2

Input
n = 2, k = 52
Output
zz

Example 3

Input
n = 5, k = 5
Output
aaaaa

Constraints

  • 1 <= n <= 10^5
  • n <= k <= 26 * n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getSmallestString = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest String With A Given Numeric Value — Solution

Smallest String With A Given Numeric Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Smallest String With A Given Numeric Value is a medium coding problem on strings and greedy, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The numeric value of a lowercase letter is its position in the alphabet (a = 1, b = 2, …, z = 26), and the numeric value of a string is the sum of the values of its letters — for example "abe" has value 1 + 2 + 5 = 8.

Given integers n and k, return the lexicographically smallest string of length n whose numeric value is exactly k.

Example 1

Input: n = 4, k = 30
Output: aabz
Explanation: 1 + 1 + 2 + 26 = 30.

Example 2

Input: n = 2, k = 52
Output: zz

Example 3

Input: n = 5, k = 5
Output: aaaaa

Constraints

  • 1 <= n <= 10^5
  • n <= k <= 26 * n

Hints for Smallest String With A Given Numeric Value

  1. Hint 1

    To be lexicographically small, the string should start with as many as as possible.

  2. Hint 2

    So push the value to the end: fill from the right with the largest letters that still leave at least 1 for every earlier position.

  3. Hint 3

    Start with all a (value n), then distribute the remaining k − n from the last position backwards, at most 25 extra per position.

How to solve Smallest String With A Given Numeric Value

Start from n copies of a and add the remaining value k − n from the right end, each position taking up to 25 more (turning it into at most z).

Approach

  1. Create an array of n letters, all a, and set extra = k − n.
  2. For i from n − 1 down to 0: add d = min(25, extra) to position i and subtract it from extra.
  3. Return the letters as a string.

Why it works

Among all strings of value k, the smallest one maximises its run of leading as, and then keeps the first non-a letter as small as possible. Filling from the right puts as much value as possible into the later positions (each takes the maximum, 25 extra), so the earliest positions take only what is left, which is the least they can take. Since k ≤ 26n, the extra value always fits.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Filling from the left with zs produces the largest string, not the smallest.
  • Each letter is worth at least 1, so subtract n before distributing.
  • String concatenation in a loop can be quadratic in some languages — build a character array.

Reference solution

Python

def getSmallestString(n: int, k: int) -> str:
    res = ["a"] * n
    extra = k - n
    i = n - 1
    while extra > 0:
        d = min(25, extra)
        res[i] = chr(97 + d)
        extra -= d
        i -= 1
    return "".join(res)

Java

public static String getSmallestString(int n, int k) {
    char[] res = new char[n];
    Arrays.fill(res, 'a');
    int extra = k - n;
    for (int i = n - 1; i >= 0 && extra > 0; i--) {
        int d = Math.min(25, extra);
        res[i] = (char)('a' + d);
        extra -= d;
    }
    return new String(res);
}

C++

string getSmallestString(int n, int k) {
    string res(n, 'a');
    int extra = k - n;
    for (int i = n - 1; i >= 0 && extra > 0; i--) {
        int d = min(25, extra);
        res[i] = (char)('a' + d);
        extra -= d;
    }
    return res;
}

JavaScript

var getSmallestString = function(n, k) {
    var res = [];
    for (var i = 0; i < n; i++) res.push(0);
    var extra = k - n;
    for (var j = n - 1; j >= 0 && extra > 0; j--) {
        var d = Math.min(25, extra);
        res[j] = d;
        extra -= d;
    }
    var out = [];
    for (var t = 0; t < n; t++) out.push(String.fromCharCode(97 + res[t]));
    return out.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms