1663. Smallest String With A Given Numeric Value LeetCode Solution
In this guide, you will get 1663. Smallest String With A Given Numeric Value LeetCode Solution with the best time and space complexity. The solution to Smallest String With A Given Numeric Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Smallest String With A Given Numeric Value
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.
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 <= 105
n <= k <= 26 * n
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1663. Smallest String With A Given Numeric Value LeetCode Solution in C++
class Solution {
public:
string getSmallestString(int n, int k) {
string ans;
for (int i = 0; i < n; ++i) {
const int remainingLetters = n - 1 - i;
const int rank = max(1, k - remainingLetters * 26);
ans += 'a' + rank - 1;
k -= rank;
}
return ans;
}
}; /* code provided by PROGIEZ */
1663. Smallest String With A Given Numeric Value LeetCode Solution in Java
class Solution {
public String getSmallestString(int n, int k) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; ++i) {
final int remainingLetters = n - 1 - i;
final int rank = Math.max(1, k - remainingLetters * 26);
sb.append((char) ('a' + rank - 1));
k -= rank;
}
return sb.toString();
}
} // code provided by PROGIEZ
1663. Smallest String With A Given Numeric Value LeetCode Solution in Python
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
ans = []
for i in range(n):
remainingLetters = n - 1 - i
rank = max(1, k - remainingLetters * 26)
ans.append(chr(ord('a') + rank - 1))
k -= rank
return ''.join(ans) # code by PROGIEZ
