BinarySearch 0712 Lexicographically Smallest Non-Palindromic String

Problem statement

https://binarysearch.com/problems/Lexicographically-Smallest-Non-Palindromic-String/

Solution

Equal to Leetcode 1328. Break a Palindrome.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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 ""