Greedy O(n) Solution with Image Explanation
Leetcode 1663. Smallest String With A Given Numeric Value\n\nBy Frank Luo\n\n# Greedy\n\nAs we want to minimize the lexicographical order of the constructed str
[Leetcode](https://leetcode.com/) [1663. Smallest String With A Given Numeric Value](https://leetcode.com/problems/smallest-string-with-a-given-numeric-value/)\n\n***By Frank Luo***\n\n# Greedy\n\nAs 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.\n\nSuppose we are currently constructed to a certain position, as the picture below shows.\n\n![Greedy](https://assets.leetcode.com/users/images/95d7fbe8-01ec-4594-a79a-d773da5b1bcc_1647914018.2457857.png)\n\nIncluding this position, there are still $n_{rest}$ left to fill in, the remaining sum of these rest positions is $k_{rest}$.\n \nIf we put a letter $\\textit{ch}$, and so the remaining $n_{rest} - 1$ positions with the sum is $k_{rest}$ must satisfy:\n\n$$\n1 \\times (n_{rest}-1) \\leq k_{rest}-ch \\leq 26 \\times (n_{rest}-1)\n$$\n\ncan be:\n\n$$\nk_{rest}-26 \\times (n_{rest}-1 ) \\leq ch \\leq k_{rest}-1 \\times (n_{rest}-1)\n$$\n\nSo $\\textit{ch}$ \n\n1. $k_{rest} - 26 \\times (n_{rest}-1) \\leq 0$, we choose the character $a$;\n2. $k_{rest} - 26 \\times (n_{rest}-1) \\gt 0$,  we choose the character corresponding to this value.\n \nLet\'s write the code:\n \n```java\n    public String getSmallestString_greedy(int n, int k) {\n        StringBuilder sb = new StringBuilder(n);\n        for (int rest = n; rest >= 1; rest--) {\n            int bound = k - 26 * (rest - 1);\n            if (bound > 0) {\n                char ch = (char) (bound + \'a\' - 1);\n                sb.append(ch);\n                k -= bound;\n            } else {\n                sb.append(\'a\');\n                k--;\n            }\n        }\n\n        return sb.toString();\n    }\n```\n \n## Analysis\n\n- **Time Complexity**: $O(n)$\n- **Space Complexity**: $O(n)$\n\n--------------------------\n\nAll suggestions are welcome. \nIf you have any query or suggestion please comment below.\nPlease upvote\uD83D\uDC4D if you like\uD83D\uDC97 it. Thank you:-)\n\nExplore More [Leetcode Solutions](https://leetcode.com/discuss/general-discussion/1868912/My-Leetcode-Solutions-All-In-One). \uD83D\uDE09\uD83D\uDE03\uD83D\uDC97\n\n
['Greedy', 'Java']