Break a Palindrome

Question states that given a palindrome, create the next lexicographical string that turns it no longer into a palindrome.

Ex.

abccba

aaccba

To solve this, you convert the next letter which is not an ‘a’ to an ‘a’ so that it becomes the next string. This will always be the next lexicographical string.

For the case where all the letters are ‘a’

aaaaaaaa

aaaaaaab

You want the very last letter to be converted to ‘b’. This will be lexicographically next.

Finally, the last special case would be a single letter

a

Here, the output will be an empty string, because a single letter will always be a palindrome of itself.

Pseudocode

function breakPalindrome
    base case single letter
        return empty string
    iterate thru first half of the palindrome
        when letter is not an 'a'
            return palindrome with letter replaced as 'a'
    return palindrome with last letter replaced as 'b' if it gets here

Python

This is what the code would look like.

if(len(palindrome) == 1):
            return ""
        for i in range(len(palindrome)//2):
            if(palindrome[i] != 'a'):
                return palindrome[:i] + 'a' + palindrome[i+1:]
        return palindrome[:-1] + 'b'

Results

Success

Details

Runtime: 54 ms, faster than 47.20% of Python3 online submissions for Break a Palindrome.

Memory Usage: 13.9 MB, less than 13.13% of Python3 online submissions for Break a Palindrome.

Complexity Analysis:

Time: O(N)

Space: O(N)

where N is the size of palindrome