[Python] short greedy O(n) solution, explained
We need to replace one symbol and to get the smallest string as possible. First, we try to change elements on the smaller positions: imagine we have string xyzy
We need to replace one symbol and to get the smallest string as possible. First, we try to change elements on the smaller positions: imagine we have string `xyzyx` - where `x, y, z` can be any symbols. If `x` is not equal to `"a"`, then if we replace this symbol with `"a"` we will break palindrome and it will be as small as possible. However if `x = "a"`, it is not optimal to replace it to say `"b"`, we can only make our string bigger. So, we move to the next element `y` and so on. Notice that we can not change `z` in this case, because we will not break palindrome property.\n\nWhat happens, if we reached the last element and were not able to apply strategy above? Then we have string like this `aaaaaa..aaaaaa` or `aaaaaa...z...aaaaaa`, where `z` can be any symbol. In this case to get the smalles string as possible we need to replace last symbol to `"b"`. Also there is case when `n = 1`, and we can not break palindrome property so we return `""`.\n\n#### Complexity\nIt is `O(n)` for time and for space.\n\n#### Code\n```python\nclass Solution:\n    def breakPalindrome(self, pal):\n        n = len(pal)\n        for i in range(n//2):\n            if pal[i] != "a": return pal[:i] + "a" + pal[i+1:]\n        return pal[:-1] + "b" if n > 1 else ""\n```\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Greedy']