# 1328. Break a Palindrome

Question Link is here.

This is a daily challenge problem.

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

# Solution

First, we are guaranteed that the input string is Palindrome, therefore, we only need to go through the first half of the string.

Than, we start analyse the problem.

It's obvious that a string with length of 1 can not be made not a Palindrome. So when len(s) == 0, we return an empty string.

We want to build the lexicographically smallest solution, thus, we want to place some char with 'a'. And this char need to have the smallest possible index. I.E. The first char that is not 'a'.

The problem is almost solved, becasuse we didn't consider a scenario that the string only contains 'a'. In this scenario, we just need to replace the last char to b to make the string not Palindrome.

The solution is shown below.

class Solution:
    def breakPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return ""
        s = list(s)
        length = len(s) // 2
        for i in range(length):
            if s[i] == 'a':
                continue
            else:
                s[i] = 'a'
                return "".join(s)
        s[-1] = 'b'
        return "".join(s)

This solution has Time complexity of $O(n)$. And the space complexity of $O(n)$