Поиск самой длинной подстроки без повторяющихся символов: супер-упрощенное объяснение

Решения на Python

📌 Постановка задачи

Имея строку s, найдите длину самой длинной подстроки без повторяющихся символов.

Пример:

Input: s = "abcabcb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Решение 💡

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

1. Мы можем создать все подстроки без повторяющихся символов, а затем найти ту, которая имеет наибольшую длину.
2. Для приведенного выше примера у нас есть подстроки без повторяющихся символов следующим образом: a, ab, abc, b, bc, bca, c, ca, cab. Вы можете вручную проверить.
3. Теперь вы можете убедиться, что самая длинная подстрока имеет длину 3, что является требуемым ответом.

Преобразование нашей логики в код

• У нас есть строка. Как и в случае с массивом, мы должны пройтись по каждому элементу строки. Так что будет for loop.
• Нам нужно создавать подстроки по мере того, как мы зацикливаемся, и разбивать подстроку, когда мы достигаем повторяющегося символа.
• Мы можем использовать переменную с именем maxLen, чтобы отслеживать длину этой подстроки и обновлять ее, если она больше текущей maxLen.

Вот реализация того же самого на Python:

Я рекомендую вам сделать пробный прогон одного из примеров, чтобы правильно визуализировать, как он работает. Вы заметите, что один цикл for здесь фактически лишний и может быть удален.

Как оптимизировать?

Два for loops всегда плохой знак. Временная сложность O(n^2). Следующий вопрос, который вы должны задать себе, — сможете ли вы сделать это, используя один цикл.

• Во-первых, мы можем поставить условие для крайних случаев. Если вся строка уникальна, мы видим, что требуемый ответ — это длина самой строки. Это также относится к сценарию с пустой строкой. Мы можем найти то же самое, используя функцию set() в python, которая возвращает набор только уникальных элементов типа данных, будь то массив или строка. Обратите внимание, как он используется в коде. Он пригодится во многих местах.
• Когда мы перемещаемся по строке в цикле, есть только две возможности: данный символ в строке либо является частью самой длинной подстроки, либо нет. Как мы это определяем? Если этот символ уже появился в подстроке, которую мы строим, мы разрываем ее там, сохраняем длину до этой точки и начинаем новую подстроку с этого символа.

Прочтите комментарии к коду и выполните пробный прогон на примере.

Можем ли мы сделать еще лучше?

Логически подумав, может быть сложно самостоятельно придумать другое эффективное решение. Тем не менее, с некоторыми тонкими намеками и базовыми знаниями, возможно, мы сможем что-то понять.

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

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

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

А пока вы можете изучить решение этой проблемы с литкодом с помощью подхода, обсуждаемого в этом блоге. Я рассмотрел решение Python. Посмотрите, можете ли вы прийти с кодом Javascript.