LeetCode 1663 - Smallest String With A Given Numeric Value

The problem asks us to construct a lowercase string of length n such that the sum of the numeric values of its character

leetcodemediumstringgreedy

LeetCode Problem 1663

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

Problem Understanding

The problem asks us to construct a lowercase string of length n such that the sum of the numeric values of its characters equals k, while also ensuring the resulting string is lexicographically smallest.

Each lowercase letter has a numeric value equal to its position in the alphabet:

  • a = 1
  • b = 2
  • c = 3
  • ...
  • z = 26

For example, the string "abe" has a numeric value of:

1 + 2 + 5 = 8

We are given two integers:

  • n, the required length of the string
  • k, the required total numeric value

Our task is to return the smallest lexicographical string satisfying both constraints.

Lexicographical ordering behaves like dictionary ordering. A string is smaller if it has a smaller character at the earliest position where the strings differ. This detail is extremely important because it tells us how to optimize the construction.

For example, consider:

  • "aay" → starts with "aa"
  • "aby" → starts with "ab"

Since 'a' < 'b' at the second character, "aay" is lexicographically smaller.

The challenge is not merely finding any valid string, but the smallest possible one.

The constraints provide important insight:

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

The lower bound k >= n guarantees that a solution exists, because we can always fill the string with 'a', which contributes 1 each.

The upper bound k <= 26 * n guarantees we never need more than 'z' in any position.

Since n can be as large as 100,000, exponential or brute-force enumeration is impossible. We need a solution close to linear time.

Several edge cases immediately stand out:

  • When k = n, every character must be 'a'
  • When k = 26 * n, every character must be 'z'
  • When only a small adjustment beyond all 'a' characters is needed
  • When large values force multiple trailing 'z' characters
  • When the optimal string contains a mix of 'a', one middle character, and several 'z' characters

The problem guarantees a valid answer always exists, so we never need to handle impossible inputs.

Approaches

Brute Force Approach

A brute-force solution would try all possible lowercase strings of length n, calculate their numeric values, and return the lexicographically smallest valid one.

We could imagine generating strings recursively:

  • At each position, try every character from 'a' to 'z'
  • Continue until length n
  • Compute total numeric value
  • Keep the smallest valid candidate

This works conceptually because it explores every possible solution and guarantees correctness.

However, the number of possible strings is:

$$26^n$$

Even for small values of n, this becomes computationally impossible.

For example:

  • n = 10 gives roughly 1.4 × 10^14 possibilities
  • n = 100000 is unimaginably large

Thus, brute force is entirely infeasible.

Key Insight for an Optimal Solution

To obtain the lexicographically smallest string, we want the leftmost characters to be as small as possible.

Since 'a' is the smallest letter, our first instinct should be:

  1. Fill the string with 'a'
  2. Distribute the remaining value strategically

Initially, an all-'a' string has value:

$$n$$

So we define:

$$remaining = k - n$$

This represents the extra numeric value we still need.

Now comes the greedy observation:

To minimize lexicographical order, we should place larger letters as far right as possible.

Why?

Because earlier characters have more impact on lexicographical ordering than later ones.

For example:

  • "aay" is smaller than "aya"

Even though both contain the same letters, the earlier 'a' makes the first string smaller.

So we greedily work from right to left, adding as much value as possible to each character.

Each position already contributes 1 because it starts as 'a'.

A character can gain at most:

$$26 - 1 = 25$$

extra value.

Thus, for each position from right to left:

  • Add as much as possible, capped at 25
  • Convert the character accordingly
  • Reduce the remaining value

This greedy strategy guarantees lexicographical minimality.

Approach Time Complexity Space Complexity Notes
Brute Force O(26^n) O(n) Enumerates all possible strings
Optimal Greedy O(n) O(n) Greedily fills from right to left

Algorithm Walkthrough

  1. Start by assuming every character is 'a'.

Since 'a' contributes 1, an all-'a' string has total value n. 2. Compute the extra value still needed.

We calculate:

$$remaining = k - n$$

This tells us how much value must be added beyond the baseline 'a' characters. 3. Create a character array of size n, initialized with 'a'.

We use an array because strings are immutable in many languages, and we will modify characters efficiently. 4. Traverse from the rightmost position to the leftmost.

We move right to left because larger letters should appear later to keep the string lexicographically smallest. 5. At each position, add as much extra value as possible.

Each character can gain at most 25 extra points.

Compute:

$$extra = \min(25, remaining)$$ 6. Update the current character.

Convert the character from 'a' to:

$$chr(ord('a') + extra)$$

Examples:

  • 0 → 'a'
  • 1 → 'b'
  • 25 → 'z'
  1. Subtract the added value.

Update:

$$remaining -= extra$$ 8. Continue until all extra value has been distributed. 9. Join the character array into a string and return it.

Why it works

The key invariant is that earlier characters are always kept as small as possible.

At every step, we greedily assign the maximum possible value to the rightmost available position. Since lexicographical order prioritizes earlier characters, delaying large letters toward the end guarantees minimality.

Any alternative solution placing a larger character earlier would necessarily be lexicographically larger.

Therefore, this greedy strategy always produces the smallest valid string.

Python Solution

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        chars = ['a'] * n
        
        remaining = k - n
        
        for i in range(n - 1, -1, -1):
            if remaining == 0:
                break

            extra = min(25, remaining)
            chars[i] = chr(ord('a') + extra)
            remaining -= extra

        return ''.join(chars)

The implementation begins by initializing an array of 'a' characters of length n. This gives us the smallest possible starting point while contributing a baseline value of n.

We then calculate remaining = k - n, which represents how much extra numeric value must still be distributed.

Next, we iterate from the last index toward the beginning. For each position, we greedily assign as much extra value as possible, capped at 25, because 'a' already contributes 1 and 'z' contributes 26.

The character is updated using ASCII arithmetic with ord() and chr(). Finally, once all extra value has been assigned, we join the character list into the final string.

Go Solution

func getSmallestString(n int, k int) string {
	chars := make([]byte, n)

	for i := 0; i < n; i++ {
		chars[i] = 'a'
	}

	remaining := k - n

	for i := n - 1; i >= 0; i-- {
		if remaining == 0 {
			break
		}

		extra := remaining
		if extra > 25 {
			extra = 25
		}

		chars[i] = byte('a' + extra)
		remaining -= extra
	}

	return string(chars)
}

The Go implementation follows the exact same greedy strategy.

Since strings in Go are immutable, we use a []byte slice to efficiently modify characters in place. Each position starts as 'a', and we traverse from right to left, distributing extra value greedily.

Unlike Python, Go does not provide min() for integers directly, so we implement the cap manually using a conditional statement.

Integer overflow is not a concern because the constraints remain well within Go's integer limits.

Worked Examples

Example 1

Input:

n = 3, k = 27

Start with:

aaa

Baseline value:

3

Remaining:

27 - 3 = 24
Step Index Remaining Before Extra Added Character Current String
Initial - 24 - - aaa
1 2 24 24 y aay
2 1 0 0 a aay
3 0 0 0 a aay

Final answer:

"aay"

Numeric value:

1 + 1 + 25 = 27

Example 2

Input:

n = 5, k = 73

Start with:

aaaaa

Baseline:

5

Remaining:

73 - 5 = 68
Step Index Remaining Before Extra Added Character Current String
Initial - 68 - - aaaaa
1 4 68 25 z aaaaz
2 3 43 25 z aaazz
3 2 18 18 s aaszz
4 1 0 0 a aaszz
5 0 0 0 a aaszz

Final answer:

"aaszz"

Numeric value:

1 + 1 + 19 + 26 + 26 = 73

Complexity Analysis

Measure Complexity Explanation
Time O(n) We traverse the string once
Space O(n) We store the character array

The algorithm performs a single pass from right to left through n positions. Every operation inside the loop is constant time, so the total runtime is linear.

The space complexity is O(n) because we explicitly maintain an array of characters before converting it into a string.

Test Cases

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        chars = ['a'] * n
        remaining = k - n

        for i in range(n - 1, -1, -1):
            if remaining == 0:
                break

            extra = min(25, remaining)
            chars[i] = chr(ord('a') + extra)
            remaining -= extra

        return ''.join(chars)

sol = Solution()

assert sol.getSmallestString(3, 27) == "aay"  # Example 1
assert sol.getSmallestString(5, 73) == "aaszz"  # Example 2

assert sol.getSmallestString(1, 1) == "a"  # Smallest input
assert sol.getSmallestString(1, 26) == "z"  # Single max character

assert sol.getSmallestString(5, 5) == "aaaaa"  # Minimum possible k
assert sol.getSmallestString(3, 78) == "zzz"  # Maximum possible k

assert sol.getSmallestString(2, 27) == "az"  # One z at the end
assert sol.getSmallestString(2, 28) == "bz"  # Middle distribution

assert sol.getSmallestString(4, 30) == "aabz"  # Mixed letters
assert sol.getSmallestString(6, 31) == "aaaaaz"  # Mostly a's

assert len(sol.getSmallestString(100000, 100000)) == 100000  # Large n
assert len(sol.getSmallestString(100000, 2600000)) == 100000  # Large max case
Test Why
(3, 27) Validates Example 1
(5, 73) Validates Example 2
(1, 1) Smallest legal input
(1, 26) Single maximum-value character
(5, 5) Minimum possible k
(3, 78) Maximum possible k
(2, 27) Ensures rightmost greedy placement
(2, 28) Tests partial distribution
(4, 30) Verifies mixed character composition
(6, 31) Tests one large trailing character
(100000, 100000) Large-scale minimum case
(100000, 2600000) Large-scale maximum case

Edge Cases

Edge Case 1: Minimum Possible Value

When k = n, every character must be 'a'.

For example:

n = 5, k = 5

A buggy implementation might still try modifying characters unnecessarily. Our implementation correctly computes:

remaining = 0

Since no extra value is needed, the loop exits immediately and returns "aaaaa".

Edge Case 2: Maximum Possible Value

When:

k = 26 * n

every character must become 'z'.

For example:

n = 3, k = 78

The algorithm repeatedly adds 25 extra value to every position, eventually producing:

"zzz"

The greedy logic naturally handles this without any special-case code.

Edge Case 3: Partial Fill in the Middle

Sometimes the answer contains many 'a' characters, one intermediate character, and several 'z' characters.

Example:

n = 5, k = 52

Start with:

aaaaa

Remaining:

47

We fill from the right:

  • last character → z (+25)
  • second-last → w (+22)

Result:

aaawz

This case is easy to get wrong if characters are filled left to right, because that would produce a lexicographically larger string. By filling right to left, our implementation guarantees the smallest possible result.