Найдите самую длинную подстроку с k уникальными символами в заданной строке

Опубликовано: 4 Января, 2022

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

Примеры:

 «aabbcc», k = 1
Максимальное количество подстрок может быть любым из {"aa", "bb", "cc"}.

«aabbcc», k = 2
Максимальное количество подстрок может быть любым из {"aabb", "bbcc"}.

«aabbcc», k = 3
Есть подстроки с ровно 3 уникальными символами
{"aabbcc", "abbcc", "aabbc", "abbc"}
Макс - «aabbcc» с длиной 6.

«аааббб», k = 3
Есть только два уникальных символа, поэтому отображается сообщение об ошибке.

Источник: Google Interview Question.

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Метод 1 (грубая сила)
Если длина строки равна n, то может быть n * (n + 1) / 2 возможных подстрок. Простой способ - сгенерировать всю подстроку и проверить каждую, имеет ли она ровно k уникальных символов или нет. Если мы применим эту грубую силу, потребуется O (n 2 ) для генерации всех подстрок и O (n) для проверки каждой из них. Таким образом, в целом это будет O (n 3 ).
Мы можем дополнительно улучшить это решение, создав хеш-таблицу и при генерации подстрок проверять количество уникальных символов, используя эту хеш-таблицу. Таким образом, он улучшится до O (n 2 ).

Метод 2 (линейное время)
Проблема может быть решена за O (n). Идея состоит в том, чтобы поддерживать окно и добавлять элементы в окно до тех пор, пока оно не станет меньше или равно k, при необходимости обновите наш результат при этом. Если количество уникальных элементов превышает необходимое в окне, начните удалять элементы с левой стороны.
Ниже приведены реализации вышеизложенного. Реализации предполагают, что алфавит входной строки содержит только 26 символов (от «a» до «z»). Код можно легко расширить до 256 символов.

Выход:

 Максимальная длина строки: cbebebe длиной 7

Сложность времени: учитывая, что функция isValid () занимает постоянное время, временная сложность вышеуказанного решения составляет O (n).
Эта статья предоставлена Gaurav Sharma. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ