598. Smallest Word of Value
In a word game every lowercase letter has a point value equal to its place in the alphabet: a is worth 1, b is worth 2, and so on up to z which is worth 26. The value of a word is the sum of the point values of its letters.
Given a length n and a target score k, build a word of exactly n lowercase letters whose value is exactly k, and among all such words return the one that comes first in dictionary (lexicographic) order. It is guaranteed that at least one such word exists. Your solution should run in O(n) time and use O(n) space for the answer.
Example 1
- Input:
- n = 3, k = 27
- Output:
- "aay"
- Explanation:
Start with aaa (value 3); the extra 24 goes to the last letter, giving a letter worth 25, so the answer is "aay".
Example 2
- Input:
- n = 4, k = 30
- Output:
- "aabz"
- Explanation:
The extra 26 goes 25 to the last letter and 1 to the previous one, giving "aabz".
Example 3
- Input:
- n = 2, k = 2
- Output:
- "aa"
- Explanation:
The value equals the length, so every letter must be worth 1 and the word is "aa".
Constraints
1 ≤ n ≤ 1000000n ≤ k ≤ 26 * n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)