1663. Smallest String With A Given Numeric Value

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

Example 1:

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

Problem Summary

The numeric value of a lowercase character is its position in the alphabet (starting from 1), 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. A string consists of several lowercase characters, and the numeric value of the string is the sum of the numeric values of its characters. 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 whose length is equal to n and whose numeric value is equal to k. Note that if string x comes before y in dictionary order, then x is considered lexicographically smaller than y. There are the following two cases:

• x is a prefix of y;
• If i is the first position where x[i] != y[i], and x[i] comes before y[i] in the alphabet.

Solution Ideas

• Given n and k, find the lexicographically smallest string of length n such that the sum of the positions of its letters in the alphabet is k.
• After reading this problem, I directly wrote a DFS version during the contest. After the contest, I looked at its time complexity and found it was just acceptable, but I felt there was still room for optimization. DFS will enumerate all solutions, but in fact this problem only asks for the lexicographically smallest one, so when pruning in DFS, a lexicographic-order check should be added: if the newly added letter is lexicographically larger than the letter at the corresponding position in the already saved string, then return directly, because this answer definitely will not be the lexicographically smallest. See Solution 2 for the code.
• Thinking further, DFS is actually unnecessary; a for loop can directly find the lexicographically smallest string. See Solution 1 for the code.

Code

package leetcode

// Solution 1 Greedy
func getSmallestString(n int, k int) string {
    str, i, j := make([]byte, n), 0, 0
    for i = n-1; i <= k-26; i, k = i-1, k-26 {
        str[i] = 'z'
    }
    if i >= 0 {
        str[i] = byte('a' + k-1-i)
        for ; j < i; j++ {
            str[j] = 'a'
        }
    }
    return string(str)
}

// Solution 2 DFS
func getSmallestString1(n int, k int) string {
	if n == 0 {
		return ""
	}
	res, c := "", []byte{}
	findSmallestString(0, n, k, 0, c, &res)
	return res
}

func findSmallestString(value int, length, k, index int, str []byte, res *string) {
	if len(str) == length && value == k {
		tmp := string(str)
		if (*res) == "" {
			*res = tmp
		}
		if tmp < *res && *res != "" {
			*res = tmp
		}
		return
	}
	if len(str) >= index && (*res) != "" && str[index-1] > (*res)[index-1] {
		return
	}
	for j := 0; j < 26; j++ {
		if k-value > (length-len(str))*26 || value > k {
			return
		}
		str = append(str, byte(int('a')+j))
		value += j + 1
		findSmallestString(value, length, k, index+1, str, res)
		str = str[:len(str)-1]
		value -= j + 1

	}
}