Smallest String With A Given Numeric Value: Greedy from the Right

You are given two integers n and k. Every lowercase letter has a numeric value: a = 1, b = 2, all the way to z = 26. The numeric value of a string is the sum of the values of its characters. Your task is to return the lexicographically smallest string of length n whose numeric value equals k.

This is LeetCode 1663. Smallest String With A Given Numeric Value.

Why this problem matters

Greedy algorithms shine when you need to optimize one property (lexicographic order) while satisfying a constraint (numeric sum). The trick is figuring out where to be greedy. In many string problems, being greedy from the left means keeping left characters as small as possible. That principle shows up again and again in problems that ask for the "smallest" or "earliest" arrangement.

This problem is a clean example of that pattern. Once you see how to pack large values at the right end of the string, you have a reusable template for any problem that asks you to build a lexicographically minimal sequence under a sum constraint.

The key insight

To get the lexicographically smallest string, you want the leftmost characters to be as small as possible. That means pushing all the "weight" to the right side of the string. Here is the strategy:

1. Start by filling every position with 'a' (value 1 each). This accounts for n out of the total k.
2. You have remaining = k - n still to distribute.
3. Iterate from the rightmost position to the left. At each position, upgrade the character by as much as possible, up to 25 (since 'a' + 25 = 'z'), or by whatever remaining you have left.
4. Stop once remaining hits zero.

By filling from the right, the leftmost characters stay as 'a' for as long as possible, which is exactly what lexicographic minimality demands.

The solution

def get_smallest_string(n: int, k: int) -> str:
    result = ['a'] * n
    remaining = k - n

    for i in range(n - 1, -1, -1):
        add = min(25, remaining)
        result[i] = chr(ord('a') + add)
        remaining -= add
        if remaining == 0:
            break

    return ''.join(result)

The function starts by creating a list of n copies of 'a'. Then it calculates how much extra value needs to be spread across the string. Walking from the last index toward the first, it upgrades each character by the smaller of 25 (the maximum upgrade from 'a' to 'z') and the remaining value. Once the remaining value is fully distributed, the loop breaks early. Finally, the list is joined into a string and returned.

Visual walkthrough

The walkthrough shows n=3 and k=27. After initializing all three positions to 'a' (total value 3), there are 24 remaining units to distribute. Starting from position 2, the algorithm adds all 24 to that slot, turning 'a' into 'y'. The remaining drops to zero, so positions 0 and 1 stay as 'a'. The result is "aay".

Complexity analysis

The time complexity is O(n) because the loop iterates over at most n positions once. In practice, it often terminates early once remaining reaches zero, but the worst case is a full pass.

The space complexity is O(n) for the result array. No auxiliary data structures are needed beyond the output itself.

The building blocks

1. Greedy lexicographic construction

When you need the smallest string satisfying a constraint, the pattern is always the same: keep the leftmost characters as small as possible. This means you make decisions about the right side first and let the left side benefit from whatever slack remains.

result = ['a'] * n
remaining = k - n

By starting with all 'a's, you establish the smallest possible baseline. Everything that follows only modifies positions from the right, preserving the small left characters.

2. Value distribution from right to left

The core loop walks backward through the string, upgrading each position by the maximum it can absorb.

for i in range(n - 1, -1, -1):
    add = min(25, remaining)
    result[i] = chr(ord('a') + add)
    remaining -= add

The min(25, remaining) expression handles both cases: when there is more than enough value to make a 'z', and when the remaining value is less than a full upgrade. This two-case pattern (cap at max, or use what is left) is the bread and butter of greedy distribution problems.

Edge cases

• k equals n. Every character must be 'a', since the minimum total for n characters is n. The result is a string of n copies of 'a'.
• k equals 26 times n. Every character must be 'z', since the maximum total for n characters is 26n. The result is a string of n copies of 'z'.
• n equals 1. The string is a single character whose value equals k. Just convert k directly to the corresponding letter.
• remaining is a multiple of 25. The rightmost positions fill up to 'z' evenly, and the rest stay as 'a'. No partial upgrade needed.
• remaining is less than 25. Only the last character gets upgraded. All others remain 'a'.
• Large n with small k. Most of the string is 'a', with a small bump near the end. The early-exit condition (if remaining == 0: break) makes the loop efficient.

From understanding to recall

The code for this problem is short, but the reasoning behind it is what you want to internalize. The greedy pattern here, starting from the smallest possible answer and upgrading from the back, applies to a whole family of problems. When you review this, focus on why filling from the right produces the lexicographically smallest result. Picture the string as a row of slots, each starting at 'a', and imagine pouring value into the rightmost slot first until it overflows to 'z', then moving left.

Practice writing the loop from memory. The key details are: initialize with 'a', compute remaining, iterate right to left, cap each upgrade at 25, and break when done. Once that sequence is automatic, you can adapt it to harder variants without re-deriving the logic.

Related posts

• Orderly Queue - Another string optimization problem using greedy reasoning about character placement
• Largest Number - Greedy string construction for numeric optimization
• Remove Duplicate Letters - Greedy character selection for lexicographically smallest result

Greedy problems reward pattern recognition. The more of these you internalize, the faster you spot the right strategy in new problems. CodeBricks helps you build that recognition through spaced repetition, so the patterns stick long after you first solve them.