Найти максимальную длину цепочки "cvv" + "ccv" в строке

Question

Необходимо определить максимальную длину цепочки подстрок вида "согласная + любая буква + гласная", идущих подряд, в данной строке. Доступный алфавит - "AOCDF". Хотелось узнать, почему необходимо сбрасывать счетчик к двум, а не к нулю? (counter = 2)

s = open('24.txt').readline() #len(s) == 262144
max_ = 0
counter = 0
for i in range(0,len(s)-2,3):
    s = s.replace('D', 'c').replace('C','c').replace('A','v').replace('O','v').replace('F','c')
    if ((s[i]+s[i+1]+s[i+2]) in 'ccv') or ((s[i]+s[i+1]+s[i+2]) in 'cvv'):
        counter += 1
        max_ = max(max_,counter)
    else:
        counter = 2 #почему необходимо определять c = 2?
print(max_) # --> 6

24.txt

Answer 1

Необходимо пройти 3 последовательных цикла: 1 начинается с [0], 2 - [1], 3-[2], с шагом +3, с концом len(s)-2. Таким образом переберутся все возможные варианты, если бы цепочка начиналась: с первого / со второго / с третьего элемента. Четвертый элемент смысла рассматривать нет

Answer 2

Ваш код совсем не рабочий. Для строки DDDA он возвращает 0, а правильный ответ 3. Для полного файла он вернёт неверный ответ. Надо только вынести шесть вызовов replace из цикла.

Но задача интересная. Пусть s - строка символов длиной n. Пусть f_i - самая длинная "правильная" последовательность из троек, которая заканчивается в позиции i, 0 ≤ i < n. Что про неё можно сказать?

если i < 2, то f_i = 0;
если i ≥ 2 и тройка s_i-2s_i-1s_i неправильная, то f_i = 0;
если i ≥ 2 и тройка s_i-2s_i-1s_i правильная, то f_i = f_i-3 + 3.

Последовательность f можно построить итеративно. Причём хранить нужно только три последних значения. То есть константная память. Код ниже так и делает - f0, f1, f2 - три последних значения f, которые меняются местами по кругу. Итерация ведётся двумя итераторами для первого и третьего символа в тройке:

import sys


def longest(s):

    def gen():
        it = iter(s)
        next(it, None)
        next(it, None)

        f0, f1, f2 = 0, 0, 0
        for c1, c2 in zip(s, it):
            if c1 in 'CDF' and c2 in 'AO':
                f0, f1, f2 = f1, f2, f0 + 3
                yield f2
            else:
                f0, f1, f2 = f1, f2, 0


    return max(gen(), default=0)


print(longest(sys.stdin.read()))

Полсекунды и ответ готов:

$ time python cvv-ccv.py < 24.txt 
18

real  0m0.414s
user  0m0.416s
sys   0m0.000s

БЛОГ НА HUSL

Найти максимальную длину цепочки "cvv" + "ccv" в строке

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