Sponsored
Sponsored
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').
Time Complexity: O(n), as we iterate over the string once.
Space Complexity: O(n), for the storage of the result string.
1class Solution {
2 public String getSmallestString(int n, int k) {
3 char[] result = new char[n];
4 for (int i = 0; i < n; i++) {
5 result[i] = 'a';
6 }
7 k -= n; // Reduce k by the sum of 'a's
8 for (int i = n - 1; i >= 0 && k > 0; --i) {
9 int add = Math.min(k, 25);
10 result[i] += add;
11 k -= add;
12 }
13 return new String(result);
14 }
15
16 public static void main(String[] args) {
17 Solution sol = new Solution();
18 System.out.println(sol.getSmallestString(3, 27));
19 }
20}In Java, we initialize a character array filled with 'a'. By decreasing k by the length of the string, we go backwards to increment characters' values until the requisite total is met. The solution exploits the nature of character manipulation in arrays to modify the lexicographical ordering optimally.
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.
Time Complexity: O(n)
Space Complexity: O(n) for storing the resulting string.
#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;
}The C++ solution uses standard procedures in manipulating strings similarly to arrays, iterating from the back to optimize both the value and order by utilizing the least numbers ahead.