Задача "Нелюбимая буква" на Python

Question

Нелюбимая буква

Антон недавно изучил английский алфавит и его самая нелюбимая буква - буква y. Если у него есть строка s, то он делает из нее строку s1, удаляя все буквы «y» из строки s (оставляя все остальные символы в том же порядке). Он сгенерировал новую строку t путем соединения s и s1. Другими словами, t=s+s1.

Вам дана строка t. Найдите такую строку s, которую использовал Антон, чтобы сгенерировать строку t.

У меня был код:

def generate(s):
    d = ''
    for i in s:
        if i != 'y':
            d += i
    return d
a = input()
d = ''
for i in range(len(a)):
    d += a[i]
    if a[i+1:] == generate(d):
        print(d)
        exit()
print(0)

Пишет 'Превышено ограничение времени на тесте 11'. Как оптимизировать код, он работал не более чем за одну секунду для любой строки?

Answer 1

как по мне вы усложнили код и он мог бы выглядеть так:

text = 'testereser'

res = text[:(len(text)+text.count('t')) // 2]

print(res)

смотрите какая логика:

новая строка содержит старую строку и старую строку без буквы 't'

если подсчитать сколько букв 't' было удалено (по сути сколько букв 't' содержится в новой строке поскольку они остались только в первоначальной строке),

то сложил кол-во букв с длиной новой строки мы получим длину удвоенной первоначальной строки,

а разделив ее на 2 получим длину исходной строки.

Зная длину исходной строки можно выделить ее из итоговой.

Answer 2

Вы на каждой итерации цикла сравниваете очередной кусок строки со всей оставшейся строкой. Это сложность O(n**2) получается.

Я бы попробовал посчитать все буквы в строке, кроме y, получившуюся длину разделил пополам и взял подстроку до такой длины с конца строки. Сложность O(n) вроде бы получается.

БЛОГ НА HUSL

Задача "Нелюбимая буква" на Python

Ответы (2 шт):