1573: Два символи


Submit solution


Points:10
Time limit:0.5s
Memory limit:64M
Author:

Problem type

Задається рядок S довжиною N , який мiстить лише символи латинського алфавiту у нижньому регiстрi. Ви повиннi видаляти деякi символи до тих пiр, поки рядок не буде складатися лише з двох рiзних символiв, якi чергуються у рядку. При видаленнi вибраного символа видаляються всi його входження у рядок. Ваше завдання - залишити найдовший рядок, який мiстить всього два символи, що чергуються.

Наприклад, розглянемо рядок abaacdabd. Якщо ви видалите символ a, то залишиться рядок bcdbd. Тепер, вилучення символу c залишається рядок bdbd довжиною 4. Утворився рядок, який відповідає описаним вимогам.

Формат вхідних даних

Перший рядок мiстить цiле число N (1 <= N <= 1000) - довжина рядка. Наступний рядок мiстить S.

Формат вихідних даних

Вивести максимальну довжину шуканого рядка. Якщо описаний рядок утворити неможливо, то вивести 0.

Приклад вхідних даних

10
beabeefeab

Приклад вихідних даних

5

Пояснення

Шуканий рядок буде babab


Comments


  • 2
    BOGDANBZ
     commented on Aug. 21, 2020 edit 2

    Довольно простая полнопереборная, если можно так выразиться)), задача. Что делаем: перебираем все возможные пары (назовём их a и b) символов латиницы. Далее в дополнительную строку F записываем все символы S, которые равны выбранным a и b. ВАЖНО: проверить состоит ли эта строка F из 2 различных символов(может быть так, что одного или даже двух символов (из а и b) в строке S не нашлось). Теперь всё хорошо: есть "лишняя" строка F, в которой "лежат" только символы a и b. За один цикл проходим по строке F и смотрим, чередуются ли символы в ней. Это можно сделать, например, так(я сознательно не публикую всего решения. Это лишь фрагмент):

    welldone:=true;

    for j:=1 to length(F)-2 do

    if F[j]<>F[j+2] then welldone:=false;

    Если и тут всё хорошо(символы в строке F чередуются), находим максимальную длину среди таких строк. Можно так: maxLen:=max(maxLen, length(F)); - это пишем прямо в переборе циклами(каждый раз пересчитываем). Можно и в массив записать, чем сведём задачу к базовой. Как угодно;)

    (Кстати, maxLen написано в стиле нижнегоВерблюжьегоРегистра (ссылка на предыдущую задачу контеста:) )) Вот и всё: выводим на экран maxLen; Асимптотика по времени: O(27х26/2хN). Спросите, почему 27*26/2? Читаем комбинаторику(сочетания С из 27 по 2).