Найти наибольшую подстроку, являющуюся радугой Помогите! Срочно

Question

Найти наибольшую подстроку, являющуюся радугой Помогите! Срочно

Максим Волнкин Ученик (99), на голосовании 1 месяц назад

Задачка с Т-Поколения
После проливного дождя в Т-стране вышло солнце и небо окрасилось в три цвета:
красный (R),
зеленый (G),
синий (B).
Маленький мальчик Петя успел записать все цвета, которые он увидел, в одну строку s. Но вот незадача: ему стало интересно узнать размер самой большой радуги, которая
была на небе, а считать он умеет только до двух.
Радугой называется строка, имеющая вид R..RG..GB..B. Например, строка RRGGBB является радугой, а RGGBB и GGRRBB - нет.
Помогите Пете! Найдите наибольшую подстроку строки, которую он записал, являющуюся радугой, и выведите её длину. Если ни одна подстрока не является радугой, выведите 0.

Формат входных данных:

В первой строке записано одно целое число n (1 6 n 6 105).
Во второй строке записана строка s состоящая из n символов R, G, B.

Формат выходных данных:

Выведите одно число - длину наибольшей подстроки, являющейся радугой.

Входные данные:

7
RRRGGBB 6

8
RRGGGBBB 0

Мой код(проваливает тест 9 по ответу, возможно слишком длинная строка там):

 input() 
w=input().upper() 
n=w.count('B') 
t='R'*n+'G'*n+'B'*n 
if "RGB" in w: 
    print(0) 
else: 
    if t in w: 
        print(3*n) 
    else: 
        if "RRGGBB" in w: 
            print(6) 
        else: 
            print(0)

Дополнен 3 месяца назад

Решено. Помогли на киберфоруме в теме задач на python

Answer 1

Для решения этой задачи можно использовать следующий алгоритм:
1. Просматриваем строку слева направо и ищем первый символ R. Запоминаем его позицию в строке.
2. Далее просматриваем строку справа налево и ищем первый встретившийся символ B. Запоминаем его позицию.
3. Если между позициями символов R и B есть символы G, то проверяем, образуют ли они радугу. Для этого сравниваем позиции символов R и G. Если позиция символа G находится между позициями R и B, то радуга найдена. Иначе переходим к следующему символу R.
4. Находим наибольшую радугу среди всех радуг, найденных на предыдущем шаге.
5. Выводим длину найденной наибольшей радуги.

Вот пример реализации этого алгоритма на Python:

 def find_rainbow(s):
    max_length = 0
    start = 0  # Позиция первого символа R
    for i in range(len(s)):
        if s[i] == 'R':
            start = i
            break
    end = len(s) - 1  # Позиция последнего символа B
    while start < end:
        g_pos = start + 1
        while g_pos < end and s[g_pos] != 'G':
            g_pos += 1
        b_pos = end - 1
        while b_pos >= g_pos and s[b_pos] != 'B':
            b_pos -= 1
        if g_pos > start and b_pos < end:  # Радуга найдена
            length = b_pos - start + 1
            if length > max_length:
                max_length = length
        start = g_pos + 1  # Переходим к следующей возможной радуге
    return max_length

n = int(input())
s = input()
result = find_rainbow(s)
print(result)