[Java] Smallest String With A Given Numeric Value | easy explanation
\n\nProblem disection and solution approach\nSince there is a total order on the set of strings (as defined in task), a greedy approach constructing the solutio
\n\n**Problem disection and solution approach**\nSince there is a total order on the set of strings (as defined in task), a greedy approach constructing the solution is sufficient, as for each index i of a string of length n, choosing the optimal character according to the order is possible because of it (can compare lex. order of any two strings). Since for the lexicographic order only considers the characters up until the first inequal one, and we must reach a total character value, a greedy approach using the largest possible character from behind is optimal.\n\n**Implementation**\nAs we need a lookup for value - character, we can use a static array (initialization at compile time), where the index holds the character value. Since we have to use at least n value to create a string of length n (all a\'s), we deduce this from k before starting. This way, we can directly use the array indices 0 indexed. We now fill the solution string from behind, always trying to take the maximal character our budget and the length of the alphabet allows (min 25, avail), and deduce the used value from the goal. As the size of the solution is known, we can directly initialize an array of the right size, saving time not having to append & collect characters, as String construction can use the char array in const time.\n\nTime: O(n) | 10ms, 85%\nMemory: O(max(len alphabet, n)) | 39.4 MB, 30%\n\nHope everything is clear now, if you liked it please leave an upvote for others to profit as well :) \n\n\n```\n    public String getSmallestString(int n, int k) {\n        char[] sol = new char[n];\n        final char[] chr = {\'a\',\'b\',\'c\',\'d\',\'e\',\'f\',\'g\',\'h\',\'i\',\'j\',\'k\',\'l\',\'m\',\'n\',\'o\',\'p\',\'q\',\'r\',\'s\',\'t\',\'u\',\'v\',\'w\',\'x\',\'y\',\'z\'};\n        int avail = k - n;\n        for(int i=0; i < n; i++){\n            int c = Math.min(25, avail);\n            sol[n-i-1] = chr[c];\n            avail -= c;\n        }\n        \n        return new String(sol);\n    }\n```
['Array', 'Java']