C++ | one line solution, fast solution and explanation |O(n) or can O(1)?
1. One line solution\nThe solution can be combined by three kind of string, so we have the one line solution. \nC++\nclass Solution {\npublic:\n    string getSm
# 1. One line solution\nThe solution can be combined by three kind of string, so we have the one line solution. \n```C++\nclass Solution {\npublic:\n    string getSmallestString(int n, int k) {\n\t\treturn string(n-(k-n)/25-((k-n)%25!=0), \'a\') + string(((k-n)%25!=0),\'a\'+(k-n)%25) + string((k-n)/25,\'z\');\n\t}\n};\n```\n\nThe truth is that my one line code is made from this following code. \nBut code become slow if you use this one line solution. So I prefer\nthe following fast solution. It\'s faster to be executed and easier to be read. \n# 2. Fast solution\n```C++\nclass Solution {\npublic:\n    string getSmallestString(int n, int k) {\n        int total = k-n;\n        int z_cnt = total / 25;\n        int middle_val = total % 25;\n        string ans = string(n,\'a\');\n        int i = n-1;\n        for(int j =0;j<z_cnt ;i--,j++)ans[i]=\'z\';\n        if(i>=0) ans[i]=\'a\'+middle_val;\n        return ans; \n\t}\n};\n```\n\n# 3. Explanation of the fast solution \nAt the first, we would try our best to find the lexicographically smallest string. \nSo the solution will like aaaaa?zzzzz. So we will be intresting on three thing\n(1) how many a?\n(2) what ? it is ?\n(3) how many z?\n\n\nIn the original problem, there are input n,k with this mapping table 1\n```txt\n 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26\n```\nBut we can get simple observation if we can change our view into mapping table 2\n```txt\n 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 \n```\nand focus on the value `k-n`. The observation become simple.\nLet me explain following.\n\n```txt\ncase n=3, k=27 (k-n=24)\n24 = 0+0+24 -> "aay"  (refer mapping table 2)\n\ncase n=5, k=73 (k-n=68)\n68 = 0+0+18+25+25 -> "aaszz" (refer mapping table 2)\n\ncase n=4, k=54  (k-n = 50) \n50 = 0+0+25+25 -> "aazz" (refer mapping table 2)\n```\n\nThus, this observation is good for us to write a code for it.\nThat\'s why fast solution look like that.\n\n\n# 4. Complexity analysis for fast solution\n**Time complexity O(n)**\nBecause allocate n number of memory with time O(n) and use time O(n) to process  rewirte z in the result.\n**Space complexity O(n)**\nBecause output string is using n number of space. \nBut if some people think output space should not be in space complexity, then they will think this as a  space O(1) solution. \n\n\n\n# 5. What if time complexity of memory allocation can be faster?\nIf the time complexity of memory allocation can be O(1) and your can control where to allocated, then \nthe time complexity will be O(1) for one line solution\n\nFor example, a realtime system might use an heap allocator like TLSF (Two-Level Segregate Fit), which has a O(1) allocation cost.  http://www.gii.upv.es/tlsf/ \n\nif we have the such system, then one line solution is the best choice because time complexity is O(1). \nBut for almost case, fast solution with time complexity O(n) always be the good solution. \n
['C']