Первая олимпиада Олмат.Программирование. 23.02.26

Тема: Биотехнологии Уровень: Новичок

📜 Пятая находка

Вы обнаружили древний сервер биотехнологической лаборатории. На нём хранились фрагменты ДНК, записанные в текстовом виде.

Учёные выяснили, что перед синтезом живых организмов система искала самый длинный стабильный участок цепочки — фрагмент без повторяющихся пар нуклеотидов.

Почему это было важно? Повторяющиеся комбинации соседних нуклеотидов повышали вероятность мутаций — так называемых генетических выбросов.

Тебе предстоит восстановить алгоритм древней системы и определить длину самого длинного стабильного фрагмента.

🧠 Немного о технологии

ДНК состоит из четырёх типов нуклеотидов:

A — аденин C — цитозин G — гуанин T — тимин

В задаче ДНК представлена строкой, состоящей только из символов A, C, G, T.

Теперь критерий стабильности изменён.

Стабильный фрагмент — это последовательность символов, в которой не повторяется ни одна пара соседних нуклеотидов.

Под парой понимаются два соседних символа строки.

Важно: пары считаются одинаковыми независимо от порядка символов. Например:

• AC и CA — одна и та же пара;
• GT и TG — одна и та же пара.

Если такая пара встречается в фрагменте более одного раза (в любом порядке), возникает выброс.

Выбросы — это повторение одной и той же пары нуклеотидов внутри рассматриваемого участка.

Наша цель — найти максимально длинный участок без повторяющихся пар.

⚙️ Алгоритм в биологии

В реальной биологии и биоинформатике подобные алгоритмы используются при анализе геномов, РНК и белковых последовательностей.

Когда учёные исследуют ДНК:

• ищут уникальные участки генома для разработки ПЦР‑праймеров;
• определяют зоны повышенного риска мутаций;
• анализируют повторяющиеся мотивы, связанные с генетическими заболеваниями;
• сравнивают участки ДНК разных организмов.

📌 Задача

Дана строка S — последовательность нуклеотидов.

Необходимо определить длину самой длинной подстроки, в которой ни одна пара соседних символов не повторяется (при этом пары XY и YX считаются одинаковыми).

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

Одна строка S (1 ≤ |S| ≤ 10^5), состоящая только из символов A, C, G, T.

Ограничения

• 1 ≤ |S| ≤ 100000
• Используются только символы A, C, G, T

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

Вывести одно число — длину самого длинного фрагмента, удовлетворяющего условию.

📘 Примеры

Пример 1

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

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

Пояснение: пары — AC, CG, GT, TA, AC. Пара AC повторяется, поэтому максимальный корректный фрагмент — ACGTA или CGTAC.

Пример 2

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

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

Пояснение: пара AA повторяется. Любой допустимый фрагмент может содержать не более одной пары AA.

Пример 3

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

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