помогите решить задачу на (Python)

Question

Текстовый файл состоит из символов A, B, C, D, E.

Определите максимальное число идущих подряд символов в файле, удовлетворяющих условию: среди выбранных символов не встречается символа “A”, который идёт раньше символа “B”.

Например, подряд идущие символы “BCBAD” подходят под это условие, а последовательность символов “DCACBB” - не подходит. Для выполнения этого задания следует написать программу.

Начало файла 24.txt

CDBABBEBEB...

я решил задачу так

   def max_sequence(filename):
    with open(filename, 'r') as file:
        data = file.read()
    max_len = 0
    current_len = 0
    for i in range(len(data) - 1):
        if data[i] == 'A' and data[i + 1] == 'B' and (i + 2 < len(data) and data[i + 2] == 'B'):
            current_len = 0
        else:
            current_len += 1
        if current_len > max_len:
            max_len = current_len
    return max_len

print(max_sequence('24.txt'))

но это решение не верное. Помогите решить задачу

Answer 1

Расстояние между A и B может быть любым, поэтому проверки вида data[i + 1] == 'B' естественно не будут работать.

Алгоритм по идее должен быть такой:

Используете три указателя - на начало последовательности, на встреченную последней букву A и на текущий обрабатываемый символ
Когда натыкаетесь на A в очередной раз, то запоминаете в указатель на A её позицию (пока A не уйдёт из "окна" весь кусок до B будет нам бесполезен)
Когда натыкаетесь на B, то сдвигаете указатель начала на символ после этой A (см. примечание выше, этот бесполезный кусок стал актуальным)
В остальных случаях если длина между текущим указателем и начальным больше текущего максимума, запоминаете её в максимуме
Ну и увеличиваете позицию конца на 1
И так пока строка не закончится

Там ещё будут детали инициализации, проверок на конец строки и т.д., но в целом это алгоритм сложности O(n), потому что правый указатель всё время двигается вперёд и никаких циклов внутри нет, только отдельные действия по условиям.

БЛОГ НА HUSL

помогите решить задачу на (Python)

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