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.
1using System;
2
3public class Solution {
4 public string GetSmallestString(int n, int k) {
5 char[] result = new char[n];
6 for (int i = 0; i < n; i++) result[i] = 'a';
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] = (char)(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 Console.WriteLine(sol.GetSmallestString(3, 27));
19 }
20}In C#, a character array is set to 'a', with successive modifications from the back to augment the overall numeric value as needed. Utilizing arrays allows us to manipulate individual characters directly to fit the problem constraints.
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.
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 C# implementation uses a structured approach, introducing characters initially as 'a' and adjusting progressively as we approach the left-hand bound of operations, always respecting the valid sum total prescribed.