Разбор задачи «Поиск самого длинного стабильного фрагмента ДНК»

Идея задачи

Дана строка S, состоящая из символов A, C, G, T.

Нужно найти длину самой длинной подстроки, в которой не повторяется ни одна пара соседних символов, причём пары считаются одинаковыми без учёта порядка:

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

Например, в строке ACGTAC пары соседних символов такие:

• AC
• CG
• GT
• TA
• AC

Пара AC встретилась дважды, значит вся строка не подходит.

Ключевое наблюдение

Условие задано не на отдельных символах, а на парах соседних символов.

Если мы рассматриваем подстроку S[L..R], то внутри неё находятся пары:

• (L, L+1)
• (L+1, L+2)
• ...
• (R-1, R)

То есть подстрока длины k содержит k - 1 соседних пар.

Значит задача сводится к поиску самого длинного окна, в котором все такие пары различны.

Это очень похоже на классическую задачу про самую длинную подстроку без повторяющихся элементов, только элементами здесь являются не символы, а нормализованные пары соседей.

Как сравнивать пары

Так как XY и YX считаются одинаковыми, каждую пару надо привести к каноническому виду.

Например:

• AC → AC
• CA → AC
• TG → GT

Удобно закодировать символы так:

• A -> 0
• C -> 1
• G -> 2
• T -> 3

Тогда для пары берём два кода, сортируем их по возрастанию и получаем идентификатор:

id = min(a, b) * 4 + max(a, b)

Всего возможных пар немного: 4 * 4 = 16.

Это значит, что можно хранить массив lastPos размера 16, где будет лежать последняя позиция появления каждой пары.

Метод двух указателей

Будем поддерживать окно S[L..R].

При движении правой границы R вправо появляется новая пара (R-1, R).

Что делать, если пара встретилась впервые?

Просто расширяем окно.

Что делать, если такая пара уже есть в текущем окне?

Нужно сдвинуть левую границу L вправо так, чтобы предыдущее вхождение этой пары вышло из окна.

Пусть такая же пара раньше заканчивалась в позиции p. Тогда она была парой (p-1, p).

Чтобы убрать её из окна, нужно сделать так, чтобы левая граница стала не левее p, то есть:

L = p

Но сдвигать L нужно только если старая пара действительно находится внутри текущего окна. Это верно тогда и только тогда, когда:

p >= L + 1

Потому что пары в окне S[L..R] заканчиваются в позициях от L+1 до R.

Почему это работает

Мы всегда поддерживаем инвариант:

в текущем окне S[L..R] все пары соседних символов различны.

Когда добавляется новая пара:

• если конфликта нет, инвариант сохраняется;
• если конфликт есть, мы двигаем L минимально возможным образом, чтобы удалить старое вхождение конфликтной пары.

После этого в окне снова нет повторов, и можно обновить ответ.

Каждая граница двигается только вправо, поэтому алгоритм работает за линейное время.

Пошаговый пример

Рассмотрим строку:

ACGTAC

Пары:

• AC
• CG
• GT
• TA
• AC

Идём слева направо:

1. R = 0 — одна буква, ответ 1
2. R = 1 — добавили пару AC, всё хорошо, ответ 2
3. R = 2 — добавили CG, всё хорошо, ответ 3
4. R = 3 — добавили GT, всё хорошо, ответ 4
5. R = 4 — добавили TA, всё хорошо, ответ 5

6. R = 5 — добавили AC, но такая пара уже была

   • старое вхождение заканчивалось в позиции 1
   • значит нужно сделать L = 1
   • новое окно: CGTAC, длина 5

Итоговый ответ: 5.

Оценка сложности

Время

Каждый индекс правой границы рассматривается один раз, левая граница тоже двигается только вперёд.

Итого:

O(n)

Память

Используется массив из 16 элементов:

O(1)

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

static int code(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3; // 'T'
}

static int pair_id(char x, char y) {
    int a = code(x), b = code(y);
    if (a > b) swap(a, b);   // XY == YX
    return a * 4 + b;        // 0..15
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = (int)s.size();

    if (n == 0) {
        cout << 0 << '\n';
        return 0;
    }
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }

    vector<int> lastPos(16, -1);

    int L = 0;
    int ans = 1;

    for (int R = 0; R < n; R++) {
        if (R >= 1) {
            int id = pair_id(s[R - 1], s[R]);
            int p = lastPos[id];

            // пара (p-1, p) лежит в окне тогда и только тогда,
            // когда p >= L + 1
            if (p != -1 && p >= L + 1) {
                L = p;
            }

            lastPos[id] = R;
        }

        ans = max(ans, R - L + 1);
    }

    cout << ans << '\n';
    return 0;
}

Реализация на Python

import sys


def code(c: str) -> int:
    if c == 'A':
        return 0
    if c == 'C':
        return 1
    if c == 'G':
        return 2
    return 3  # 'T'


def pair_id(x: str, y: str) -> int:
    a, b = code(x), code(y)
    if a > b:
        a, b = b, a   # XY == YX
    return a * 4 + b  # 0..15


def main() -> None:
    s = sys.stdin.readline().strip()
    n = len(s)

    if n == 0:
        print(0)
        return
    if n == 1:
        print(1)
        return

    last_pos = [-1] * 16

    L = 0
    ans = 1

    for R in range(n):
        if R >= 1:
            pid = pair_id(s[R - 1], s[R])
            p = last_pos[pid]

            # старая конфликтная пара ещё внутри окна
            if p != -1 and p >= L + 1:
                L = p

            last_pos[pid] = R

        ans = max(ans, R - L + 1)

    print(ans)


if __name__ == "__main__":
    main()

Частые ошибки

1. Считать AC и CA разными парами

Это нарушает условие задачи. Перед сравнением пару нужно нормализовать.

2. Хранить пары как строки и использовать тяжёлые структуры

Это можно сделать, но здесь алфавит очень маленький, поэтому проще и быстрее кодировать пары числами от 0 до 15.

3. Неправильно двигать левую границу

Если старая конфликтная пара заканчивалась в p, то нужно делать именно:

L = p

а не p + 1 и не p - 1.

4. Проверять повторяемость символов, а не пар

Условие относится не к буквам, а именно к соседним парам.