Метод двух указателей. Равное количество двух букв в подстроке

Question

Текстовый файл состоит не более чем из 10**6 заглавных букв латинского алфавита. Определите максимальную длину подстроки, содержащую равное количество букв A и B. Для выполнения этого задания следует написать программу.

f = open('24_10131.txt')
s = f.readline()
# s = 'TTTATTTBTTTTTTTTTTTTTTTTTTATBA'

l = 0 #левый указатель
mx = 0
q_a = 0
q_b = 0
for r in range(len(s)): # правый указатель
    if s[r] == 'A':
        q_a += 1
    if s[r] == 'B':
        q_b += 1

    while q_b > q_a:

        if s[l] == 'B':
            q_b -= 1
        l+=1
    while q_a > q_a:
        if s[l] == 'a':
            q_a -= 1
        l+=1
    if q_a == q_b:
        mx = max(mx, r - l + 1)


print(mx)

Как учитывать наличие одинакового кол-ва букв А и B при поиске максимальной подстроки?

Answer 1

Эту задачу можно решить с использованием словаря, содержащего в качестве ключей разность между количествами A и B от начала до текущей позиции, а значение - первая позиция, когда такая разность встретилась.

import random, string
s = ''.join(random.choice(string.ascii_uppercase[:4]) for i in range(10))
print(s)

diffpos = {0:-1}
diff = 0
maxx = 0
for i, c in enumerate(s):
    if c=='A':
        diff += 1
    elif c=='B':
        diff -= 1
    if diff in diffpos:
        maxx = max(maxx, i - diffpos[diff])
    else:
        diffpos[diff] = i
print(maxx)

БЛОГ НА HUSL

Метод двух указателей. Равное количество двух букв в подстроке

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