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^5n <= k <= 26 * n
Hints for Smallest String With A Given Numeric Value
Hint 1
To be lexicographically small, the string should start with as many
as as possible.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.
Hint 3
Start with all
a(valuen), then distribute the remainingk − nfrom 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
- Create an array of
nletters, alla, and setextra = k − n. - For
ifromn − 1down to 0: addd = min(25, extra)to positioniand subtract it fromextra. - 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
nbefore 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