Метод 1: метод скользящего окна
Один эффективный метод поиска самой длинной подстроки с k уникальными символами — использование метода скользящего окна. Вот как это работает:
- Инициализировать два указателя, левый и правый, оба указывают на начало строки.
- Создайте словарь или хеш-карту, чтобы отслеживать количество каждого символа в текущем окне.
- Инициализируйте переменную max_length, чтобы сохранить максимальную длину подстроки.
- Перемещайте правый указатель по строке, перемещая ее по одному символу за раз.
- Увеличить количество символов в правом указателе словаря.
- Если количество уникальных символов в словаре превышает k, переместите левый указатель вправо и уменьшите счетчик символов у левого указателя в словаре, пока количество уникальных символов снова не станет k.
- Обновить max_length, если длина текущего окна (справа – слева + 1) больше max_length.
- Повторяйте шаги с 4 по 7, пока правый указатель не достигнет конца строки.
В конце процесса max_length будет длиной самой длинной подстроки с k уникальными символами.
Метод 2: подход грубой силы
Другой подход — метод перебора, который предполагает проверку всех возможных подстрок заданной строки. Мы можем перебирать каждый символ в строке и рассматривать его как начальную точку подстроки. Затем для каждой начальной точки мы можем проверить все возможные подстроки, чтобы найти самую длинную из k уникальных символов. Этот метод имеет временную сложность O(n^3) и не так эффективен, как метод скользящего окна.