Greedy solution (readable code with explanation)
Approach\nTo make the lexicographically smallest string, we spend the cost at leftest character.\n\nFor example, if s = \'cb\', k = 1, we must use this cost at 
# Approach\nTo make the lexicographically smallest string, we spend the cost at leftest character.\n\nFor example, if `s = \'cb\', k = 1`, we must use this cost at the first character, unless it already becomes to `\'a\'`.\n\nThus, we only need to consider two cases:\n* If there\'s enough k, make character become `\'a\'`.\n* If there\'s no enough k, make character minus `k`.\n> You may have question why we minus `k` rather than add `k`? Because if we can achieve to smaller character using this `k`, that means it has enough `k` to make character become `\'a\'`.\n\nHow to calculate the distance between character `c` and `\'a\'`? \n* `c` minus to `\'a\'`:  distance is `c - \'a\'`\n* `c` plus to `\'a\'`: distance is `\'a\' + 26 - c = 26 - (c - \'a\')`\n* Choose the smaller one.\n\n# Complexity\n- Time complexity: $O(n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python\nclass Solution:\n    def getSmallestString(self, s: str, k: int) -> str:\n        out = []\n        for c in s:\n            distance = ord(c) - ord(\'a\')\n            distance = min(distance, 26 - distance)\n            # If there\'s enough k to make c become \'a\'\n            if distance <= k:\n                out.append(\'a\')\n                k -= distance\n            else:\n                out.append( chr(ord(c) - k) )\n                k = 0\n        return \'\'.join(out)\n```
['Python3']