Python3. Greedily force "a" at start
Intuition\nSeems like need to greedily set the first letter to "a" or the lowest possible, then the second letter etc.\n\n# Approach\nGo letter by letter, pick 
# Intuition\nSeems like need to greedily set the first letter to "a" or the lowest possible, then the second letter etc.\n\n# Approach\nGo letter by letter, pick the minimal cost of changing to "a" or the lowest possible letter.\n\n# Complexity\n- Time complexity:\n$$O(n)$$, scan the string\n\n- Space complexity:\n$$O(n)$$, additional space to allocate the result $$t$$\n\n# Code\n```\nclass Solution:\n    def getSmallestString(self, s: str, k: int) -> str:\n        # to get lexicographically smallest, need to try to place the lowest letters first\n        # k is the budget, just greedily spend it trying to make the first letter as close to a as possitble\n\n        # trivial case\n        if k == 0:\n            return s\n\n        t = []\n        it = iter(s)\n        for c in it:\n            # convert ASCII to 0-25 range\n            c = ord(c) - 97\n            # cost to "a" through "z"\n            upCost = 26 - c\n            # cost to "a" by decreasing\n            downCost = c\n\n            # if there is no path to "a", do as much as possible\n            if upCost > k and downCost > k:\n                # no budget is left, append the rest of s and break\n                t.append(chr(97 + c - k))\n                t.extend(it)\n                break\n\n            # take "a" with the minimal cost\n            t.append(\'a\')\n            k -= min(upCost, downCost)\n\n        return "".join(t)\n```
['Python3']