Smallest String With A Given Numeric Value solution and explanation
9 more videos on this problem
Smallest String With A Given Numeric Value | Leetcode 1663 | Greedy | Day-22Ayushi Sharma · 11:51 · 2K views
Smallest String With A Given Numeric Value | Live Coding with Explanation | Leetcode #1663Algorithms Made Easy · 7:36 · 2K views
Smallest String With A Given Numeric Value | Leetcode 1663 | Maths | Live coding session 🔥🔥Coding Decoded · 6:44 · 1K views
Smallest String With A Given Numeric ValueCode with Alisha · 11:13 · 1K views
Smallest String With A Given Numeric Value | Leetcode 1663 | leetcode solutionEasyLeetcode · 12:24 · 1K views
Smallest String With A Given Numeric Value | Leetcode 1663Coding Decoded · 10:57 · 892 views
LeetCode 1663. Smallest String With A Given Numeric Value - Interview Prep Ep 111Fisher Coder · 12:57 · 841 views
Leetcode - Smallest String With A Given Numeric Value (Python)Timothy H Chang · 11:11 · 682 views
1663. Smallest String With A Given Numeric Value (Leetcode Medium)Programming Live with Larry · 11:46 · 377 views
Daily Leetcode #721: Mar 22, 2022 - 1663. Smallest String With A Given Numeric ValueProgramming Live with Larry · 10:10 · 259 views
The 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 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').
def getSmallestString(n, k):
result = ['a'] * n
k -= n # Reducethe k by the sum of 'a's
index = n - 1
while k > 0:
add = min(k, 25)
result[index] = chr(ord('a') + add)
k -= add
index -= 1
return ''.join(result)
# Example Usage
print(getSmallestString(3, 27))class Solution {
public String getSmallestString(int n, int k) {
char[] result = new char[n];
for (int i = 0; i < n; i++) {
result[i] = 'a';
}
k -= n; // Reduce k by the sum of 'a's
for (int i = n - 1; i >= 0 && k > 0; --i) {
int add = Math.min(k, 25);
result[i] += add;
k -= add;
}
return new String(result);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.getSmallestString(3, 27));
}
}#include <iostream>
#include <string>
std::string getSmallestString(int n, int k) {
std::string result(n, 'a');
k -= n; // Reduce k by the sum of 'a's
for (int i = n - 1; i >= 0 && k > 0; --i) {
int add = std::min(k, 25);
result[i] += add;
k -= add;
}
return result;
}
int main() {
int n = 3, k = 27;
std::cout << getSmallestString(n, k) << std::endl;
return 0;
}function getSmallestString(n, k) {
let result = Array(n).fill('a');
k -= n; // Reduce k by the sum of 'a's
for (let i = n - 1; i >= 0 && k > 0; i--) {
let add = Math.min(k, 25);
result[i] = String.fromCharCode(result[i].charCodeAt(0) + add);
k -= add;
}
return result.join('');
}
// Example usage
console.log(getSmallestString(3, 27));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* getSmallestString(int n, int k) {
char* result = (char*)malloc((n + 1) * sizeof(char));
memset(result, 'a', n);
result[n] = '\0';
k -= n; // Reduce k by the sum of 'a's
for (int i = n - 1; i >= 0 && k > 0; --i) {
int add = k < 25 ? k : 25;
result[i] += add;
k -= add;
}
return result;
}
int main() {
int n = 3, k = 27;
char *result = getSmallestString(n, k);
printf("%s\n", result);
free(result);
return 0;
}using System;
public class Solution {
public string GetSmallestString(int n, int k) {
char[] result = new char[n];
for (int i = 0; i < n; i++) result[i] = 'a';
k -= n; // Reduce k by the sum of 'a's
for (int i = n - 1; i >= 0 && k > 0; i--) {
int add = Math.Min(k, 25);
result[i] = (char)(result[i] + add);
k -= add;
}
return new string(result);
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.GetSmallestString(3, 27));
}
}Using Python, one can leverage lists to handle mutable string representations before joining them into a single output string. After initializing a list with 'a' characters, we iterate backwards, adjusting each character to elevate the total numeric value without disturbing the growing lexicographical sequence.
Time Complexity: O(n)
Space Complexity: O(n) for the list storing the characters.
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.
def getSmallestString(n, k):
result = ['a'] * n
k -= n
index = n - 1
while k > 0:
add = min(k, 25)
result[index] = chr(ord('a') + add)
k -= add
index -= 1
return ''.join(result)
# Example usage
print(getSmallestString(3, 27))class Solution {
public String getSmallestString(int n, int k) {
char[] result = new char[n];
for (int i = 0; i < n; i++) {
result[i] = 'a';
}
k -= n;
for (int i = n - 1; i >= 0 && k > 0; --i) {
int add = Math.min(k, 25);
result[i] += add;
k -= add;
}
return new String(result);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.getSmallestString(3, 27));
}
}#include <iostream>
#include <string>
std::string getSmallestString(int n, int k) {
std::string result(n, 'a');
k -= n;
for (int i = n - 1; i >= 0 && k > 0; --i) {
int add = std::min(k, 25);
result[i] += add;
k -= add;
}
return result;
}
int main() {
int n = 3, k = 27;
std::cout << getSmallestString(n, k) << std::endl;
return 0;
}function getSmallestString(n, k) {
let result = Array(n).fill('a');
k -= n;
for (let i = n - 1; i >= 0 && k > 0; i--) {
let add = Math.min(k, 25);
result[i] = String.fromCharCode(result[i].charCodeAt(0) + add);
k -= add;
}
return result.join('');
}
// Example usage
console.log(getSmallestString(3, 27));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* getSmallestString(int n, int k) {
char* result = (char*)malloc((n + 1) * sizeof(char));
memset(result, 'a', n);
result[n] = '\0';
k -= n; // Overall reduction
for (int i = n - 1; i >= 0 && k > 0; --i) {
int add = k < 25 ? k : 25;
result[i] += add;
k -= add;
}
return result;
}
int main() {
int n = 3, k = 27;
char *result = getSmallestString(n, k);
printf("%s\n", result);
free(result);
return 0;
}using System;
public class Solution {
public string GetSmallestString(int n, int k) {
char[] result = new char[n];
for (int i = 0; i < n; i++) result[i] = 'a';
k -= n;
for (int i = n - 1; i >= 0 && k > 0; i--) {
int add = Math.Min(k, 25);
result[i] = (char)(result[i] + add);
k -= add;
}
return new string(result);
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.GetSmallestString(3, 27));
}
}This Python solution prepares a list filled with 'a', then iterates backwards from the end, conditionally augmenting values to meet required total alongside initial literals, making use of character manipulation functions natively supported by Python.
Time Complexity: O(n)
Space Complexity: O(n) while storing the resultant list data.
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).
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)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Backwards Approach | Time Complexity: O(n) |
| Incremental Forward Approach | Time Complexity: O(n) |
| Greedy | – |
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. |
Frequently asked questions
Is Smallest String With A Given Numeric Value easy or hard?
The problem is classified as Medium difficulty on LeetCode. The implementation is short, but identifying the correct greedy strategy and understanding why larger characters should be placed toward the end requires careful reasoning.
Smallest String With A Given Numeric Value Python/Java solution
Both Python and Java implementations follow the same greedy idea. Initialize a character array filled with 'a', compute the remaining value k - n, then iterate from the end adding up to 25 per position. Python typically uses a list of characters joined at the end, while Java uses a char array or StringBuilder.
How to solve Smallest String With A Given Numeric Value in O(n)?
Start by filling an array of length n with 'a', giving a base value of n. Compute the remaining value k - n and iterate from the end of the array. At each position add up to 25 extra value (turning 'a' into 'z') until the remainder becomes zero. Convert the array to a string at the end. This greedy distribution guarantees the smallest lexicographic result in O(n) time.
What is the best approach for Smallest String With A Given Numeric Value?
The greedy backwards approach is the most efficient and commonly used solution. Initialize the string with 'a' characters and distribute the remaining value (k - n) from the end of the string. This keeps larger characters toward the right, ensuring the result remains lexicographically smallest. The algorithm runs in O(n) time with O(n) space.
Is Smallest String With A Given Numeric Value asked at Google/Amazon/Meta?
Greedy string construction problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The question tests understanding of greedy decision making, lexicographic ordering, and constraint reasoning, which are common themes in coding interviews.
What data structure is used in Smallest String With A Given Numeric Value?
The solution primarily uses a character array or string builder to construct the result. The algorithm relies more on greedy logic and arithmetic rather than complex data structures, which keeps the implementation simple and efficient.
What is the time complexity of Smallest String With A Given Numeric Value?
The optimal solution runs in O(n) time because each character position is processed once. The algorithm simply distributes the remaining numeric value across the string using constant-time operations per index. Space complexity is O(n) for storing the resulting string.