[LeetCode][1663. Smallest String With A Given Numeric Value] Greedy O(n) Solution with Image Explanation

By Long Luo

This article is the solution Greedy O(n) Solution with Image Explanation of Problem 1663. Smallest String With A Given Numeric Value.

Greedy

As we want to minimize the lexicographical order of the constructed string, let’s start from the beginning of the string, select the smallest letter that satisfies the requirements each time, then we get the final answer.

Suppose we are currently constructed to a certain position, as the picture below shows.

Greedy

Including this position, there are still nrestn_{rest} left to fill in, the remaining sum of these rest positions is krestk_{rest}.

If we put a letter ch\textit{ch}, and so the remaining nrest1n_{rest} - 1 positions with the sum is krestk_{rest} must satisfy:

1×(nrest1)krestch26×(nrest1)1 \times (n_{rest}-1) \leq k_{rest}-ch \leq 26 \times (n_{rest}-1)

can be:

krest26×(nrest1)chkrest1×(nrest1)k_{rest}-26 \times (n_{rest}-1 ) \leq ch \leq k_{rest}-1 \times (n_{rest}-1)

So ch\textit{ch}

  1. krest26×(nrest1)0k_{rest} - 26 \times (n_{rest}-1) \leq 0, we choose the character aa;
  2. krest26×(nrest1)>0k_{rest} - 26 \times (n_{rest}-1) \gt 0, we choose the character corresponding to this value.

Let’s write the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String getSmallestString_greedy(int n, int k) {
StringBuilder sb = new StringBuilder(n);
for (int rest = n; rest >= 1; rest--) {
int bound = k - 26 * (rest - 1);
if (bound > 0) {
char ch = (char) (bound + 'a' - 1);
sb.append(ch);
k -= bound;
} else {
sb.append('a');
k--;
}
}

return sb.toString();
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗