Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn't a palindrome.
After doing so, return the final string.  If there is no way to do so, return the empty string.
 
Example 1:
Input: palindrome = "abccba"
Output: "aaccba"

Example 2:
Input: palindrome = "a"
Output: ""

 
Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Greedy algorithms

Starter code: class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        

Solutions:
class Solution:

	def breakPalindrome(self, palindrome: str) -> str:
		if len(palindrome) == 1:
			return ''
		for (i, val) in enumerate(palindrome):
			if val != 'a' and i != len(palindrome) // 2:
				return palindrome[:i] + 'a' + palindrome[i + 1:]
			elif val == 'a' and i == len(palindrome) - 1:
				return palindrome[:-1] + 'b'


class Solution:

	def breakPalindrome(self, s: str) -> str:
		for i in range(len(s) // 2):
			if s[i] != 'a':
				return s[:i] + 'a' + s[i + 1:]
		if s[:-1]:
			return s[:-1] + 'b'
		else:
			return ''


class Solution:

	def breakPalindrome(self, palindrome: str) -> str:
		for i in range(math.floor(len(palindrome) / 2)):
			if palindrome[i] != 'a':
				return palindrome[0:i] + 'a' + palindrome[i + 1:]
		if len(palindrome) == 1:
			return ''
		else:
			return palindrome[:-1] + 'b'