Smallest String With A Given Numeric Value - Problem

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: 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.

Input & Output

Example 1 — Basic Case
$ Input: n = 3, k = 27
Output: "aay"
💡 Note: Start with "aaa" (sum=3), need 24 more. Place 'y' (value 25) at position 2: "aay" has sum 1+1+25=27
Example 2 — Multiple Z's
$ Input: n = 5, k = 73
Output: "aaszz"
💡 Note: Start with "aaaaa" (sum=5), need 68 more. Place two 'z's and one 's': "aaszz" has sum 1+1+19+26+26=73
Example 3 — All A's
$ Input: n = 4, k = 4
Output: "aaaa"
💡 Note: Sum equals minimum possible (n), so all characters remain 'a'

Constraints

  • 1 ≤ n ≤ 105
  • n ≤ k ≤ 26 * n

Visualization

Tap to expand
Smallest String Problem: n=3, k=27Inputn=3, k=27Greedy Algorithmaaa → aayOutput"aay"String length: 3Target sum: 27aaySum: 1+1+25=27 ✓Lexicographically smallestAlgorithm: Start with 'a's, fill right-to-left with largest lettersTime: O(n) | Space: O(n) | Pattern: Greedy
Understanding the Visualization
1
Input
n=3, k=27 (need string of length 3 with sum 27)
2
Process
Start with 'aaa', then greedily place largest letters from right
3
Output
"aay" (sum = 1+1+25 = 27)
Key Takeaway
🎯 Key Insight: Start with all 'a's for lexicographic ordering, then greedily place 'z's from right to left
Asked in
Google 15 Amazon 12 Microsoft 8 Facebook 6
28.4K Views
Medium Frequency
~15 min Avg. Time
892 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen