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

<p>Return <em>the resulting string. If there is no way to replace a character to make it not a palindrome, return an <strong>empty string</strong>.</em></p>

<p>A string <code>a</code> is lexicographically smaller than a string <code>b</code> (of the same length) if in the first position where <code>a</code> and <code>b</code> differ, <code>a</code> has a character strictly smaller than the corresponding character in <code>b</code>. For example, <code>&quot;abcc&quot;</code> is lexicographically smaller than <code>&quot;abcd&quot;</code> because the first position they differ is at the fourth character, and <code>&#39;c&#39;</code> is smaller than <code>&#39;d&#39;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> palindrome = &quot;abccba&quot;
<strong>Output:</strong> &quot;aaccba&quot;
<strong>Explanation:</strong> There are many ways to make &quot;abccba&quot; not a palindrome, such as &quot;<u>z</u>bccba&quot;, &quot;a<u>a</u>ccba&quot;, and &quot;ab<u>a</u>cba&quot;.
Of all the ways, &quot;aaccba&quot; is the lexicographically smallest.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> palindrome = &quot;a&quot;
<strong>Output:</strong> &quot;&quot;
<strong>Explanation:</strong> There is no way to replace a single character to make &quot;a&quot; not a palindrome, so return an empty string.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= palindrome.length &lt;= 1000</code></li>
	<li><code>palindrome</code> consists of only lowercase English letters.</li>
</ul>

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        
        n=len(palindrome)
        
        # if its only any single letter we cant replace it still and make it non-palindrome
        # so just return empty string
        
        if n==1:
            return ""
        
        # to get lexographilcally smallest non palindrome
        # we have to observe that it would be contain 'a' first
        # but if its already have 'a' initially then 
        # the next non-'a' would be replaced with 'a'
        
        st=""
        for i in range(n):
            if palindrome[i]!='a':
                st+='a'
                st+=palindrome[i+1:]
                if st!=st[::-1]:
                    return st
                else: break
            st+=palindrome[i]
            
        # but what if all are already 'a' 'aaaaaa'
        # we need to change last letter with 'b' while still making it smallest lexographically
        
        return palindrome[:-1]+'b'


        # WITHOUT EXTRA SPACE

        # instead of using extra space for 'st'
        # what was corner case was that 'aba'
        # when we changed b it became palindrome 'aaa'
        # so with using extra space we had to check if it was palindrom or not
        # but if we just check upto half of that string we could avoid that condition
        # as it will conclude either that if we traverse upto half and no change is there 
        # it means either whole string is 'aaaa' or middle character is non-'a'
        # in both case we have to change then last character only
        
        # so we can ignore the condition with just taking loop upto n//2-1
        # and remove that st and its palindrome check
        
        n=len(palindrome)
        
        if n==1: return ''
        
        for i in range(n//2):
            if palindrome[i]!='a':
                return palindrome[:i]+'a'+palindrome[i+1:]
           
        # if conditions are 'aabaa' or 'aaaa' change last character with b
        return palindrome[:-1]+'b'
            
16400