Замените один символ в строке палиндрома, чтобы он стал непалиндромным питоном

Question

Не могли бы вы помочь со следующей задачей, с которой я столкнулся во время онлайн-интервью по программированию.

В качестве входных данных вам дается строка палиндрома, вы можете заменить только один символ в ней, и после модификации она должна соответствовать 2 следующим условиям:

1. Не будь палиндромом
2. Будьте лексикографически меньше оригинальной строки ввода

Я не смог найти никакого решения. Но вот моя логика:

Прежде всего, строки являются неизменяемыми в python, поэтому сначала нужно преобразовать их в список. Затем, возможно, используя какой-то цикл, нужно заменить элементы в списке, затем преобразовать список обратно в строку и проверить:

1. если строка - палиндром 2. если она лексикографически меньше.

Но я не понимаю, чем мне нужно его заменить? Должен ли это быть другой вложенный цикл, который будет проходить через [az]?

Answer 1

При условии, что палиндром будет содержать только строчные буквы английского алфавита (поскольку речь идет о лексикографически меньших строках), вам нужно просто следовать 3 правилам:

1. заменить первый символ, который не 'a' с 'a'
2. не пытайтесь заменить средний символ (так как это не повлияет на то, является ли строка палиндромом)
3. если ваша новая строка совпадает с вашей старой строкой, это означает, что вы не можете найти никакого решения, так что это не может быть сделано

вам не нужно проверять, является ли результат палиндромом или нет, если вы поменяли одного не среднего члена, вы знаете, что это не будет палиндром (поскольку ваш вклад гарантированно будет палиндромом), вам также не нужно преобразовать его в список, поскольку строки уже обладают всеми необходимыми функциями

код для этого может выглядеть так:

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

вы всегда можете изменить, какой персонаж вы проверяете вместо 'a' в зависимости от вашего определения "лексикографически меньше"