Smallest String With A Given Numeric Value - Solution & Explanation
Problem Statement
The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.
The numeric value of a string consisting of lowercase characters is defined as the sum of its characters' numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.
You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.
Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.
Example 1:
Input: n = 3, k = 27 Output: "aay" Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.
Example 2:
Input: n = 5, k = 73 Output: "aaszz"
Constraints:
1 <= n <= 105n <= k <= 26 * n
Approach Overview
Problem Overview: You need to construct the lexicographically smallest string of length n such that the total numeric value of its characters equals k. Each character contributes a value where 'a' = 1, 'b' = 2, ..., 'z' = 26. The challenge is distributing this total value across n characters while keeping the string lexicographically smallest.
Approach 1: Greedy Backwards Approach (O(n) time, O(n) space)
This method builds the string from right to left. Start by assuming every position contains 'a', which contributes 1 each, giving a base value of n. The remaining value k - n must be distributed across characters, but to keep the string lexicographically smallest, you add extra value starting from the end of the string. For each position, increase the character by at most 25 (turning 'a' into 'z') and subtract the used value from the remainder. Iterating backward ensures larger letters appear later, preserving the smallest possible lexicographic order. This greedy distribution works because increasing characters later in the string has the least impact on lexicographic ordering. The approach relies on simple iteration and arithmetic, making it ideal for problems involving greedy strategies and string construction.
Approach 2: Incremental Forward Approach (O(n) time, O(n) space)
This approach constructs the result from left to right while ensuring enough value remains to fill the remaining positions. At index i, you decide the smallest possible character that still allows the remaining positions to reach the total k. For the current position, iterate possible character values and check whether the remaining k can still be achieved given the bounds (remaining_positions * 1) and (remaining_positions * 26). Once a valid character is found, append it and update the remaining sum. This strategy still uses greedy reasoning but enforces feasibility constraints at every step. It is slightly more reasoning-heavy than the backward method but useful when practicing constraint-based greedy construction often seen in greedy and string problems.
Recommended for interviews: The Greedy Backwards Approach is what most interviewers expect. It reaches the optimal O(n) time with very simple logic: fill the string with 'a', then distribute the remaining value from the end. Explaining the lexicographic reasoning clearly demonstrates strong greedy intuition. Mentioning the forward feasibility approach shows deeper understanding, but the backward greedy implementation is typically preferred for clarity and speed.
Approach 1: Greedy Backwards Approach
This approach constructs the smallest lexicographical string by starting with 'a' for all characters initially. Then, it tries to modify the string starting from the end towards the beginning so that the sum of all character values becomes equal to k. We iterate backwards and replace 'a's with whatever character provides exactly the needed additional sum up to 25 (since 26 - 1 = 25, where 1 is the value of 'a').
In C, a character array is initialized to hold 'a' characters. We then reduce k by the sum of 'a's and iterate backwards to increment each character by the required amount to achieve the needed value. Finally, we return the string which represents the smallest lexicographical order.
Complexity
Time Complexity: O(n), as we iterate over the string once.
Space Complexity: O(n), for the storage of the result string.
Approach 2: Incremental Forward Approach
This approach generates the solution by starting with the smallest lexicographical letter 'a' and incrementally modifying the last possible position where it can introduce a remainder of the sum. We start assigning 'a' to fill the leftovers systematically from the beginning and increment positions forward when no more space is left towards the end.
The C code starts with an array filled with 'a's and modifies it incrementally as required. It processes the array from the back, ensuring the sum aligns with k, thus optimizing lexicographical order naturally.
Complexity
Time Complexity: O(n)
Space Complexity: O(n) for storing the resulting string.
Approach 3: Greedy
First, we initialize each character of the string to 'a', leaving a remaining value of d=k-n.
Then, we traverse the string from back to front. In each iteration, we greedily replace the current character with the character 'z' that can minimize the remaining number, until the remaining number does not exceed 25. Finally, we add the remaining number to the position we have traversed.
The time complexity is O(n), where n is the length of the string. Ignoring the space consumption of the answer, the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Backwards Approach | Time Complexity: O(n), as we iterate over the string once. |
| Incremental Forward Approach | Time Complexity: O(n) |
| Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Backwards Approach | O(n) | O(n) | Best general solution. Simple logic and minimal checks when constructing lexicographically smallest strings. |
| Incremental Forward Approach | O(n) | O(n) | Useful when practicing feasibility-based greedy decisions while building the string from left to right. |
Video Solution
Smallest String With A Given Numeric Value | Leetcode 1663 | Greedy | Day-22 • Ayushi Sharma • 2,854 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Smallest String With A Given Numeric Value easy or hard?
Smallest String With A Given Numeric Value Python/Java solution
How to solve Smallest String With A Given Numeric Value in O(n)?
What is the best approach for Smallest String With A Given Numeric Value?
Is Smallest String With A Given Numeric Value asked at Google/Amazon/Meta?
What data structure is used in Smallest String With A Given Numeric Value?
What is the time complexity of Smallest String With A Given Numeric Value?
Ready to solve this problem?
Practice Smallest String With A Given Numeric Value with our built-in code editor and test cases.
Practice on FleetCode