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 thelexicographically 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.

Examples

Example 1

1
2
3

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

1
2

Input: n = 5, k = 73
Output: "aaszz"

Constraints

  • 1 <= n <= 10^5
  • n <= k <= 26 * n

Solution

Method 1 – Greedy from the End

Intuition

To get the lexicographically smallest string, fill the string from left to right with ‘a’ as much as possible, and only use larger letters at the end to reach the required sum.

Approach

  1. Start with a string of length n filled with ‘a’.
  2. The remaining value to distribute is k - n (since each ‘a’ is 1).
  3. From the end, for each position, add as much as possible (up to 25, since ‘z’ is 26) until the remaining value is 0.
  4. Return the resulting string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    string getSmallestString(int n, int k) {
        string ans(n, 'a');
        k -= n;
        for (int i = n-1; i >= 0 && k > 0; --i) {
            int add = min(25, k);
            ans[i] += add;
            k -= add;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func getSmallestString(n int, k int) string {
    ans := make([]byte, n)
    for i := range ans { ans[i] = 'a' }
    k -= n
    for i := n-1; i >= 0 && k > 0; i-- {
        add := 25
        if k < 25 { add = k }
        ans[i] += byte(add)
        k -= add
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public String getSmallestString(int n, int k) {
        char[] ans = new char[n];
        Arrays.fill(ans, 'a');
        k -= n;
        for (int i = n-1; i >= 0 && k > 0; --i) {
            int add = Math.min(25, k);
            ans[i] += add;
            k -= add;
        }
        return new String(ans);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun getSmallestString(n: Int, k: Int): String {
        val ans = CharArray(n) { 'a' }
        var rem = k - n
        var i = n - 1
        while (i >= 0 && rem > 0) {
            val add = minOf(25, rem)
            ans[i] = (ans[i].code + add).toChar()
            rem -= add
            i--
        }
        return String(ans)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        ans = ['a'] * n
        k -= n
        i = n - 1
        while k > 0:
            add = min(25, k)
            ans[i] = chr(ord('a') + add)
            k -= add
            i -= 1
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn get_smallest_string(n: i32, k: i32) -> String {
        let mut ans = vec![b'a'; n as usize];
        let mut k = k - n;
        let mut i = n as usize;
        while k > 0 {
            i -= 1;
            let add = k.min(25);
            ans[i] += add as u8;
            k -= add;
        }
        String::from_utf8(ans).unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    getSmallestString(n: number, k: number): string {
        const ans = Array(n).fill('a');
        k -= n;
        let i = n - 1;
        while (k > 0) {
            const add = Math.min(25, k);
            ans[i] = String.fromCharCode('a'.charCodeAt(0) + add);
            k -= add;
            i--;
        }
        return ans.join("");
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. Each position is visited once.
  • 🧺 Space complexity: O(n), for the output string.