Leetcode 1328. Break a Palindrome

Problem statement

https://leetcode.com/problems/break-a-palindrome/

Solution

Use greedy strategy: try to replace first symbol not equal to a to a if possible, if we have string full of a, replace last symbol with b.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def breakPalindrome(self, pal):
        n = len(pal)
        for i in range(n//2):
            if pal[i] != "a": return pal[:i] + "a" + pal[i+1:]
        return pal[:-1] + "b" if n > 1 else ""