Abstract / Summary

Given a numeric value and a set of letter values, create the shortest possible string with that value using the smallest possible letters.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 67% (100k+ submissions).

Typical patterns to solve this problem:

• Greedy
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation constructs the lexicographically smallest string of length n whose characters sum to k when each character is mapped to a value from 1 ('a') to 26 ('z'). It does this by first allocating the minimum possible value to every position, then distributing the remaining “budget” from the rightmost character toward the left, ensuring each position never exceeds the maximum value of 26. Finally, it translates the numeric array into the corresponding lowercase letters.

Key Steps

Initialize the numeric representation

All positions start with the smallest permissible value, 1. This guarantees the string will be as small as possible before any extra budget is applied.

num = [1] * n          # each slot holds at least 1
k -= n                 # subtract the mandatory 1 per position

Distribute the remaining budget from right to left

The loop iterates from the last index down to the first. For each position it computes the maximum additional value that can be added without exceeding 26, then applies the smaller of that amount and the remaining budget k. The budget is reduced accordingly.

for i in range(n - 1, -1, -1):
    add = min(26 - num[i], k)   # allowable increment for this slot
    num[i] += add
    k -= add

Convert numeric values to characters

After the distribution phase, each entry in num lies in the range 1-26. The conversion uses the ASCII code of 'a' as a base, offset by the numeric value minus one, and concatenates the characters into the final string.

result = ""
for i in num:
    result += chr(i - 1 + ord('a'))
return result

Edge Cases Handled

When the required sum k equals the minimum possible sum (n), the initial subtraction makes k zero. The loop then adds nothing to any position, leaving the array as all ones, which translates to a string of 'a' characters.

If k equals the maximum possible sum (26 × n), after the initial subtraction the remaining budget is 25 × n. The loop will fill each position with the full increment of 25, turning every entry into 26, and the final string becomes all 'z'.

For a single-character string (n = 1), the loop runs once, and the same logic correctly produces the appropriate character based on the value of k (ranging from 'a' to 'z').

When the remaining budget is exhausted before reaching the leftmost index, the loop continues iterating but adds zero to the earlier positions, preserving their minimal value and ensuring the lexicographic minimality of the result.

Performance Optimizations

The algorithm works in linear time relative to n, performing a single pass to allocate the base values, a single reverse pass to distribute the excess, and a final pass to build the output string. By modifying the list num in place, it avoids the overhead of creating additional intermediate structures.

The use of min to cap the increment at the per-position limit eliminates the need for conditional branching, keeping the inner loop body concise and efficient.

String construction is performed via incremental concatenation inside a loop. While Python strings are immutable, the concatenation occurs only n times, matching the size of the output, and the interpreter can often optimize such patterns, resulting in acceptable performance for the problem constraints.

Overall, the code leverages straightforward arithmetic and direct array manipulation to achieve the desired result with minimal computational overhead.

Imagine there is a row of empty boxes lined up in a long magic string. Each box needs to hold a little piece of a secret code, and that piece has to be at least as small as the letter a. To start, every box gets a tiny invisible letter a inside it.

After putting those letters in, there are still some points left over from a big pile called k. To make the string as small as possible in alphabetical order, all those extra points need to be shoved into the boxes at the very end of the line. The code walks backward from the last box to the first one, stuffing as many points as it can fit into each box until the limit of twenty-six is reached. Once a box is full, the code moves to the neighbor on the left and keeps filling until all the points are used up.

Finally, the code looks at the number in each box and changes it into a letter. If the number is one, the box turns into an a. If the number is two, it turns into a b, and if it is twenty-six, it turns into a z. By placing the biggest letters at the end of the line, the string stays as tiny as possible at the beginning.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	Go
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	halfrost					Go
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality