Задача: Можно ли из слова сделать палиндром? Python

[Faserty]

Задача следующая:

Можно ли из слова сделать палиндром? Убирать можно только подстроку из трех символов (т.е. 3 символа подряд. Ни больше ни меньше.) Количество таких операций не ограничено. Палиндромом строка считается, если ее значение равно ее перевернутому значению. Т.е. это не обязательно должно быть слово(одинаковые буквы или цифры). количество символов в строке не больше 10^6

Я попытался решить, но у меня не получилось.

Пример:

Ввод: arcsinus
Вывод: YES

Ввод: abcde
Вывод: NO

s = input()
ch =list(s)
m=[]
if s == s[::-1]:
    if  (len(s) == 0):
        print("NO")
    else:
        print("YES")
        
elif len(s) > 4:
    for i in s:
        if ch.count(i)>1:
            c = s.find(i)
            if c%3==0:
                k = s.find(i,c)
                if (k - c)%4 ==0:
                    m.append(i)
                else:
                    continue
            else:
                continue
        else:
            continue
    if len(m) > 1:
        print("YES")
    else:
        print("NO")
elif 2 <len(s)<5 :
    if  (len(s)==4) and (s[1] != s[3]):
        print("NO")
    elif (len(s) == 3) and (s[0] != s [2]):
        print("NO")

[Faserty]

Faserty, я понимаю, что ошибка в этом условии

elif len(s) > 4:
    for i in s:
        if ch.count(i)>1:
            c = s.find(i)
            if c%3==0:
                k = s.find(i,c)
                if (k - c)%4 ==0:
                    m.append(i)
                else:
                    continue
            else:
                continue
        else:
            continue
    if len(m) > 1:
        print("YES")
    else:
        print("NO")

но я не понимаю почему

[ViktorR]

Не врубаюсь. Какие три символа надо удалить, чтобы из arcsinus получился палиндром?
У меня такой код:

s1 = input()   # Входная строка
s2 = s1[::-1]  # Инверсная строка
if not s1:     # Если строка пустая
    print('No')
elif s1 == s2: # и она уже палиндром
    print('Yes')
if len(s1) > 4:
    for i in range(len(s1) - 2):
        s1_left = s1[:i]        # Вырезали слева
        s1_right = s1[i + 3:]   # Вырезали справа
        m1 = s1_left + s1_right # Удалены три символа
        m2 = m1[::-1]           # Инверсия
        if m1 == m2:
            print('Yes')
            break               # Нашли вариант
    else:
        print('No')             # Нет варианта

[Faserty]

ViktorR, sinus - inu = ss
Удалять можно только три символа, которые идут рядом. Т.е. из cosinus палиндром не получится

[Valick]

Faserty, удалять можно до переворота или после переворота?

[digitalis]

А есть разница? К примеру, 11,12,13 симолы после переворота станут 97,96,95 . И что? Результат проверки на палиндромистость будет зависеть?

[ViktorR]

Faserty

sinus - inu = ss

Ну да. Только надо читать внимательнее. В вашем примере 'arcsinus'.
Первый пост:

Пример:

Ввод: arcsinus
Вывод: YES

А предложенный код подходит?

[BDA]

Сообщение от ViktorR

В вашем примере 'arcsinus'.

Сообщение от Faserty

Количество таких операций не ограничено.

arcsinus - arc - inu = ss

Сообщение от Faserty

Т.е. из cosinus палиндром не получится

Да, вроде, тоже палиндром: cosinus - cos - inu = s.
Пока мне очевиден только случай, когда остаток от деления длины строки на 3 равен 1, тогда это палиндром.

[ViktorR]

Извините, пропустил фразу:

Количество таких операций не ограничено.

[BDA]

Вроде работает (при сравнении с "очевидным" алгоритмом проверки быстро примеры расхождения не нашлись):

import string
import random
import timeit

def is_palindrome_naive(s):
    len_s = len(s)
    if len_s == 0:
        return False
    if s == s[::-1]:
        return True
    for i in range(len_s - 2):
        r = is_palindrome_naive(s[:i] + s[i + 3:])
        if r:
            return True
    return False

def is_palindrome_fast(s):
    len_s = len(s)
    if len_s == 0:
        return False
    elif len_s % 3 == 1:
        return True
    else:
        offset = (len_s + 2) % 3
        for i in range(0, len_s - offset, 3):
            for j in range(i + offset, len_s, 3):
                if s[i] == s[j]:
                    #print(i, j)
                    return True
        return False

# speed check
test_str = string.ascii_lowercase[:14]
print(timeit.timeit('is_palindrome_naive(test_str)', number = 1000, globals = globals()))
print(timeit.timeit('is_palindrome_fast(test_str)',  number = 1000, globals = globals()))

# equivalence check
i = 0
pal_count = 0
while True:
    i += 1
    s = "".join([random.choice(string.ascii_lowercase) for _ in range(random.randint(5, 10))])
    r1 = is_palindrome_naive(s)
    r2 = is_palindrome_fast(s)
    if r1 != r2:
        print(s)
        break
    if r1:
        pal_count += 1
    if i % 100000 == 0:
        print(i, pal_count)