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

Question

Это вопрос австралийской олимпиады по информатике 2019 года:

После успеха вашего последнего исследовательского проекта в области мифической ДНК вы привлекли внимание самого дьявольского существа: Медузы. Вместо волос у Медузы змеи. ДНК каждой из ее змей представлена ​​строкой заглавных букв. Каждая буква представляет собой одну из S, N, A, K или E. Ваше обширное исследование показывает, что уровень яда змеи зависит от ее ДНК. Змея имеет уровень яда x, если ее ДНК:

• имеет ровно 5x букв • начинается с x копий буквы S

• затем имеет x копий буквы N

• затем имеется x копий буквы A

• затем имеется x копий буквы K

• заканчивается x копиями буквы E.

Например, змея с уровнем яда 1 имеет ДНК ЗМЕИ, а змея с уровнем яда 3 имеет ДНК SSSNNNAAAKKKEEE. Если ДНК змеи не соответствует описанному выше формату, она имеет уровень яда 0. Медуза хотела бы, чтобы вы помогли сделать ее змей ядовитыми, удалив ноль или более букв из их ДНК. Учитывая ДНК змеи, можете ли вы определить максимальный уровень яда, который может иметь эта змея?

Можно ли с помощью двоичного поиска получить алгоритм со сложностью O (nlogn)?

Answer 1

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

изначально: l=0 r=n

когда для некоторых m=(l+r+1)/2 мы можем проверить O(n) время если мы можем получить такой уровень яда m, просто взяв сначала m буквы S, затем следующие m букв N и так далее. Если букв недостаточно, мы обновляем интервал поиска до r=m-1, в противном случае l=m

Пример: предположим, что введено SNAKESSSNNAAKKE

1. Начальные значения двоичного поиска: l=0 r=15
2. l=0 r=15 m = (l+r+1)/2 = 8
3. мы не можем получить значение яда 8, поэтому r=m-1 = 7
4. l=0 r=7 m = (l+r+1)/2 = 4
5. мы не можем получить значение яда 4, поэтому r=m-1 = 3
6. l=0 r=3 m = (l+r+1)/2 = 2
7. мы можем получить значение яда 2, поэтому l=m = 2
8. l=2 r=3 m = (l+r+1)/2 = 3
9. мы не можем получить значение яда 3, поэтому r=m-1 = 2
10. теперь, поскольку l==r, мы прекращаем двоичный поиск и делаем вывод, что ответ 2

Answer 2

Линейное время, линейное пространство:

Скажем, входная строка имеет длину n. Создайте массив 5xn, в котором 5 строк представляют совокупное количество S, N, A, K, E для каждого индекса во входном массиве. Назовем эти строки S, N, A, K и E.

Отслеживаем 5 индексов, назовем их s, n, a, k и e.

Increment `s` until `S[s]` increases by 1 (possibly at s=0). 
Increment `n` until `N[n]-N[s]=S[s]`.
Increment `a` until `A[a]-A[n]=S[s]`.
Increment `k` until `K[k]-K[a]=S[s]`.
Increment `e` until `E[e]-E[k]=S[s]`.

Повторите столько раз, сколько сможете. Окончательное число, для которого мы можем выполнить шаги приращения, дает нам ответ.

Среди массивов 5n индексов, и мы только увеличиваем их, так что это линейно по n.

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

Линейное время, постоянное пространство

Мы будем использовать те же имена индексов, что и раньше, но пусть заглавные буквы представляют совокупное количество S, N после последнего S, K после последнего N и и т.д. * каждый раз, когда мы находим соответствующую букву в индексе <= значение <code>n, a, k, e соответственно.

Установить n=s и увеличивать n, добавляя От 1 до N для каждого N мы находим, пока N=S

Проделайте то же самое для a, k, e.

Как и раньше, последнее время мы можем завершить это, мы нашли ДНК змеи.