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 * nThis 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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as we iterate over the string once.
Space Complexity: O(n), for the storage of the result string.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n) for storing the resulting string.
| Approach | Complexity |
|---|---|
| Greedy Backwards Approach | Time Complexity: O(n), as we iterate over the string once. |
| Incremental Forward Approach | Time Complexity: O(n) |
Smallest String With A Given Numeric Value | Live Coding with Explanation | Leetcode #1663 • Algorithms Made Easy • 2,624 views views
Watch 9 more video solutions →Practice Smallest String With A Given Numeric Value with our built-in code editor and test cases.
Practice on FleetCode