CODEWITHSUNDEEP
pythonpalindrome
Petr Kashlikov
Petr Kashlikov

Reputation: 111

Replace one character in palindrome string to make it non palindrome python

can you please help with following task I've encountered during online coding interview challenge.

As input you are given palindrome string, you can replace only one character in it and after modification it should meet 2 following conditions:

  1. Be not a palindrome string
  2. Be lexicographically less then original input string

I was not able to produce any solution. But here is my logic:

First of all string are immutable in python, so at first need to convert it to list. Then possibly using some kind of loop need to replace elements in list, then convert list back to string and check:

1.if string is palindrome 2.if it is lexicographically less.

But I don't understand with what I need to replace it? Should it be another nested loop which will iterate through[a-z]?

Upvotes: 0

Views: 6187

Answers (1)

AntiMatterDynamite
AntiMatterDynamite

Reputation: 1512

assuming the palindrome will only contain lowercase english alphabet (since we're talking about strings being lexicographically smaller) you need to just follow 3 rules:

  1. replace the first character that isn't 'a' with 'a'
  2. don't try to replace the middle character (since it won't affect whether or not the string is a palindrome)
  3. if your new string is the same as your old string it means you couldn't find any solution so it can't be done

you don't need to check whether the outcome is a palindrome or not, if you changed one non-middle member you know it won't be a palindrome (since your input is guaranteed to be a palindrome) you also don't need to convert it to a list since strings already have all the functionality you need

the code for this could look like this:

pali = raw_input("insert a palindrome: ")

new_string = ""

replaced = False

for i, c in enumerate(pali):
    if not replaced:
        if c > 'a' and (len(pali)/2 != i or len(pali)%2 == 0):
            new_string += 'a'
            replaced = True
        else:
            new_string += c
    else:
        new_string += c
if new_string == pali:
    print "no way to change palindrome to non palindrome and make it lexicographically smaller"
else:
    print "new non palindrome lexicographically smaller string:", new_string

you can always change what character you check for instead of 'a' depending on your definition of "lexicographically smaller"

Upvotes: 1

Related Questions