Сегодня я хочу поговорить об алгоритме поиска самой длинной подстроки с повторяющимися символами, который можно попробовать на сайте leetcode.com, и о том, как этот алгоритм надрал мне задницу. В последнее время я довольно много работаю над алгоритмами и даже начал получать от них удовольствие. Я еще не очень хорош в них, но с каждым днем ​​начинаю чувствовать себя все увереннее. Итак, приступая к этой конкретной проблеме, я чувствовал себя. К сожалению, это заняло у меня удивление и довольно много времени, чтобы понять. Давайте взглянем!

Проблема

Как показано выше, приглашение запрашивает функцию, которая принимает строку и возвращает длину самой длинной подстроки, не содержащей повторяющихся символов. Достаточно просто. В приведенном выше примере «abcabcbb» даст «abc» или 3. В то время как «pwwkew» также даст 3, поскольку самая длинная подстрока будет «wke». Обратите внимание, что «pwke» не будет правильным, это должна быть правильная подстрока.

Решение

Я знал, что это должно быть решение с двумя указателями, один из которых указывает на начальную точку, а другой определяет, как далеко мы можем пройти, прежде чем найдем повторяющийся символ. Поэтому я остановился на использовании вложенных циклов. Однако выяснить поведение циклов оказалось непросто. Нам понадобится счетчик, чтобы определить самую длинную подстроку в цикле, но мне было трудно определить, где мы будем сбрасывать цикл после достижения дубликата. В конце концов я понял, что на самом деле мне нужен внешний цикл, который будет проверять длину подстроки. Первоначально я думал, что наш первый указатель, i, из нашего внешнего цикла будет нашей отправной точкой, а j, наш внутренний указатель цикла найдет нашу конечную точку. Однако их нужно было перевернуть, а нашему внутреннему циклу нужно было проверить нашу начальную позицию и внешне сравнить ее с помощью отдельной переменной. Вот где мы закончили.

Итак, здесь происходит то, что у нас есть первый цикл, а затем второй цикл, который выполняется, только если j меньше i, где j инициализируется значением k. Затем он сравнивает s[i] с s[j], и если они равны, мы прерываем наш цикл после увеличения значения k . Мы никогда не запускаем наш внутренний цикл до тех пор, пока i не окажется впереди j в строке, и когда мы находим повторяющийся символ, мы сбрасываем проверку, чтобы начать после этого повторяющегося символа. Прежде чем мы полностью пройдемся по нашей строке, мы сверяем максимальное значение со значением i — k + 1 и возвращаем наибольшее число. У нас есть +1 для учета минимальной подстроки, поскольку мы возвращаем 0 только в том случае, если строка пуста и сравниваются индексы с отсчетом от нуля. После этого возвращаем макс. Хотя сначала я обернулся, но в конце концов мы туда добрались.

Надеюсь, это поможет! Продолжайте практиковать алгоритмы!