Using greedy without proof
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Move from brute-force thinking to an efficient approach using greedy strategy.
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 * nProblem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Greedy
3 27
5 73
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1663: Smallest String With A Given Numeric Value
class Solution {
public String getSmallestString(int n, int k) {
char[] ans = new char[n];
Arrays.fill(ans, 'a');
int i = n - 1, d = k - n;
for (; d > 25; d -= 25) {
ans[i--] = 'z';
}
ans[i] = (char) ('a' + d);
return String.valueOf(ans);
}
}
// Accepted solution for LeetCode #1663: Smallest String With A Given Numeric Value
func getSmallestString(n int, k int) string {
ans := make([]byte, n)
for i := range ans {
ans[i] = 'a'
}
i, d := n-1, k-n
for ; d > 25; i, d = i-1, d-25 {
ans[i] = 'z'
}
ans[i] += byte(d)
return string(ans)
}
# Accepted solution for LeetCode #1663: Smallest String With A Given Numeric Value
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
ans = ['a'] * n
i, d = n - 1, k - n
while d > 25:
ans[i] = 'z'
d -= 25
i -= 1
ans[i] = chr(ord(ans[i]) + d)
return ''.join(ans)
// Accepted solution for LeetCode #1663: Smallest String With A Given Numeric Value
struct Solution;
impl Solution {
fn get_smallest_string(n: i32, k: i32) -> String {
let mut k = k - n;
let n = n as usize;
let mut arr: Vec<u8> = vec![b'a'; n];
for i in (0..n).rev() {
if k > 25 {
k -= 25;
arr[i] = b'z';
} else if k > 0 {
arr[i] += k as u8;
k -= k;
} else {
break;
}
}
arr.into_iter().map(|b| b as char).collect()
}
}
#[test]
fn test() {
let n = 3;
let k = 27;
let res = "aay".to_string();
assert_eq!(Solution::get_smallest_string(n, k), res);
let n = 5;
let k = 73;
let res = "aaszz".to_string();
assert_eq!(Solution::get_smallest_string(n, k), res);
}
// Accepted solution for LeetCode #1663: Smallest String With A Given Numeric Value
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1663: Smallest String With A Given Numeric Value
// class Solution {
// public String getSmallestString(int n, int k) {
// char[] ans = new char[n];
// Arrays.fill(ans, 'a');
// int i = n - 1, d = k - n;
// for (; d > 25; d -= 25) {
// ans[i--] = 'z';
// }
// ans[i] = (char) ('a' + d);
// return String.valueOf(ans);
// }
// }
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.