Python3 - simple O(n) solution
Complexity

Time complexity:
O(n)


Space complexity:
O(n)

Code
# Complexity
- Time complexity:
O(n)

- Space complexity:
O(n)

# Code
```python3 []
class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        if k == 0:
            return s
        a = "abcdefghijklmnopqrstuvwxyz"
        res = ""
        for l in s:
            if k <= 0 or l == 'a':
                res += l
                continue

            moves_back = ord(l) - ord('a')
            moves_forward = ord('z') - ord(l) + 1
            moves = min(moves_back, moves_forward)
            if k >= moves:
                res += 'a'
            else:
                res += a[moves_back - k]
            
            k -= moves

        return res
                   

```
['Python3']