the second one in Weekly Contest 216.
leetcode Daily Challenge on January 28th, 2021.
Difficulty : Medium
Related Topics : Greedy
The numeric value of a lowercase character is defined as its position
(1-indexed)
in the alphabet, so the numeric value ofa
is1
, the numeric value ofb
is2
, the numeric value ofc
is3
, 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 to1 + 2 + 5 = 8
.You are given two integers
n
andk
. Return the lexicographically smallest string with length equal ton
and numeric value equal tok
.Note that a string
x
is lexicographically smaller than stringy
ifx
comes beforey
in dictionary order, that is, eitherx
is a prefix ofy
, or ifi
is the first position such thatx[i] != y[i]
, thenx[i]
comes beforey[i]
in alphabetic order.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.
Input: n = 5, k = 73 Output: "aaszz"
1 <= n <= 10^5
n <= k <= 26 * n
- mine
- Java
Runtime: 26 ms, faster than 70.54%, Memory Usage: 39.3 MB, less than 70.22% of Java online submissions
// O(N)time // O(N)space public String getSmallestString(int n, int k) { int count = k / 26; int mod = k % 26; StringBuilder res = new StringBuilder(); int head = n - count; while(head > 1 || mod == 0){ if(mod == 0){ count--; mod = 26; head++; } res.append('a'); mod--; head--; } res.append((char)('a' + mod - 1)); while(count > 0){ res.append('z'); count--; } return res.toString(); }
- Java
- the most votes
Runtime: 11 ms, faster than 90.05%, Memory Usage: 38.9 MB, less than 81.04% of Java online submissions
// O(N)time // O(N)space public String getSmallestString(int n, int k) { char[] ca = new char[n]; Arrays.fill(ca, 'a'); k -= n; // Guarantee each character value is at least 1. for (int i = n - 1; i >= 0 && k > 0; --i) { ca[i] += Math.min(25, k); k -= Math.min(k, 25); } return String.valueOf(ca); }