Leetcode 1663: Smallest String With A Given Numeric Value

Input: You are given two integers, `n` and `k`. The string should be of length `n` and its numeric value should be equal to `k`.

Example: n = 4, k = 34

Constraints:

• 1 <= n <= 10^5

• n <= k <= 26 * n

Output: Return the lexicographically smallest string of length `n` with a numeric value equal to `k`.

Example: "aazb"

Constraints:

• The string should be of length `n` and have a numeric value equal to `k`.

Goal: To construct the lexicographically smallest string that has the given numeric value `k` and length `n`.

Steps:

• Initialize a string of length `n` with all 'a's, since 'a' has the smallest numeric value (1).

• Subtract `n` from `k` to account for the initial 'a's.

• From the end of the string, replace 'a' with other characters (up to 'z') to achieve the desired numeric value, starting with the largest possible character (i.e., 'z').

Goal: The constraints ensure that the solution can handle large input sizes efficiently.

Steps:

• 1 <= n <= 10^5

• n <= k <= 26 * n

Assumptions:

• The value of `k` will always be valid for the given `n` according to the constraints.

• Input: n = 4, k = 34

• Explanation: The string 'aazb' has a numeric value of 1 + 1 + 26 + 2 = 34, and is the lexicographically smallest string that satisfies these conditions.

• Input: n = 6, k = 60

• Explanation: The string 'aazzzz' has a numeric value of 1 + 1 + 26 + 26 + 26 + 26 = 60, and is the lexicographically smallest string that satisfies these conditions.

Approach: The approach involves starting with a string of all 'a's and adjusting the characters from the end to reach the desired numeric value `k`.

Observations:

• The smallest string is composed of 'a's, and we need to replace some of them with higher value characters to achieve the total value `k`.

• We can use a greedy approach, modifying the string from the last position towards the first to minimize lexicographical order.

Steps:

• Initialize a string `ans` with `n` 'a' characters.

• Set `k` to `k - n` to account for the initial sum of 'a's.

• Iterate from the end of the string to the beginning, at each position replacing 'a' with the largest possible character such that the total sum of the string is equal to `k`.

Empty Inputs:

• If `n` is 1, then `k` must be between 1 and 26, inclusive.

Large Inputs:

• For large values of `n`, the algorithm should efficiently adjust the string to reach the value `k`.

Special Values:

• When `k` equals `n`, the string will consist only of 'a's.

Constraints:

• The solution must handle values of `n` up to 10^5 efficiently.

string getSmallestString(int n, int k) {
    string ans(n, 'a');
    k -= n;
    while(k > 0) {
        ans[--n] += min(25, k);
        k -= min(25, k);
    }
    return ans;
}

1 : Function Definition

string getSmallestString(int n, int k) {

Defines the function `getSmallestString` which takes integers `n` (length of the string) and `k` (target sum) as input.

2 : Variable Initialization

    string ans(n, 'a');

Initializes the string `ans` with `n` characters, all set to 'a'.

3 : Mathematical Adjustment

    k -= n;

Decreases `k` by `n` because each 'a' contributes 1 to the total sum.

4 : Looping

    while(k > 0) {

Enters a loop to adjust the string until the remaining sum `k` is zero.

5 : String Update

        ans[--n] += min(25, k);

Adjusts the last unprocessed character in `ans` by increasing its value by the smaller of 25 or `k`, ensuring it remains a valid alphabet character.

6 : Mathematical Adjustment

        k -= min(25, k);

Decreases `k` by the value added to the character, reducing the remaining sum to be distributed.

7 : Return

    return ans;

Returns the final adjusted string `ans`, which is the lexicographically smallest string meeting the criteria.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), as we modify the string in linear time.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) since we store the string.

Leetcode 1663: Smallest String With A Given Numeric Value

Explore →