Math with short proof | beats 98.62% / 99.54%
This solution is based on the fact that every output will always be of the form aaa...aaa?zzz...zzz regardless of the values of k and n.\n\nThis submission ran 
This solution is based on the fact that every output will always be of the form `aaa...aaa?zzz...zzz` *regardless* of the values of `k` and `n`.\n\nThis submission ran at **32 ms** and used **14.8 MB** of memory. At the time of submission it was **faster than 98.62%** Python3 submissions, and used **less memory than 99.54%** Python3 submissions.\n\nWe will first prove the following assertion:\n\n**Assertion:** Since we have all possible (integer) scores from 1 to 26 available, and *n &leq; k &leq; 26 &times; n*, it is **always** possible to write *k* as the sum of *n* integers from *[1,26]* with **at most one** of them not *1* or *26*.\n\nWe will construct a proof of this assertion, and then we will replicate this construction in our solution.\n\n**Proof:** Since *0 &leq; k - n*, the division algorithm guarantees that there exist **unique** integers *0 &leq; n<sub>z</sub>* and *0 &leq; r < 25* such that *k - n = 25 &times; n<sub>z</sub> + r*. Rearranging, we can rewrite this same expression as *k = 1 &times; (n - n<sub>z</sub> - 1) + (r + 1) + 26 &times; n<sub>z</sub>*. In other words, we can write *k* as the sum of *(n - n<sub>z</sub> - 1)* *1*\'s, one integer between *1* and *25*, and *n<sub>z</sub>* *26*\'s. &#8718;\n\n* Note there is nothing special about 26 in this proof, so this can be generalized to:\n**Assertion:** Let *n &geq; 1*, *b &geq; 1*, and *n &leq; k &leq; b &times; n* be integers. Then it is always possible to write *k* as the sum of *n* integers in *[1, b]*, where at most one of them is not *1* or *b*.\n\nThis assertion tells us then that all of the lexicographically smallest strings we can obtain are of the form `aaa...aaa?zzz...zzz`, with *(n - n<sub>z</sub> - 1)* `a`\'s, one character between `a` and `y`, and *n<sub>z</sub>* `z`\'s.\n\nFrom the proof, we can see that `nz = (k - n) // 25`, `na = n - nz - 1` and the score of the character in the middle is `mid = k - na - 26 * nz`. So we can construct our solution as\n```\n        return \'a\' * na + chr(96 + mid) + \'z\' * nz  # char(97) = a\n```\nThere is one problen, though. When *k = 26 &times; n* we have that *n<sub>z</sub> = n*, so there should be *n* `z`\'s, *(n - n - 1) = -1* `a`\'s, and the score of the character in between should be *26n - (-1) - 26n  = 1* (so it\'s an `a`). Theoretically the solution should work, however Python does not handle an expression as `\'a\' * (-1) + \'a\'` as one would like, and this would output `azzz...zzz` instead of the desired `zzz...zzz`.\n\nThis edge case can be fixed with\n```\n        if k == 26 * n:\n            return \'z\' * n\n```\n&#8718;\n\nThe whole solution is:\n```\nclass Solution:\n    def getSmallestString(self, n: int, k: int) -> str:\n\n        if k == 26 * n:\n            return \'z\' * n\n        \n        nz = (k - n) // 25\n        na = n - nz - 1\n        mid = k - na - 26 * nz\n        \n        return \'a\' * na + chr(96 + mid) + \'z\' * nz\n```
['Math']