3. Longest Substring Without Repeating Characters

Level - medium

Task

Given a string s, find the length of the longest substring without repeating characters.

Суть задачи

Задача "3. Longest Substring Without Repeating Characters" состоит в том, чтобы найти длину самой длинной подстроки, не содержащей повторяющихся символов.

Например, если у нас есть строка "abcabcbb", то самой длинной подстрокой без повторяющихся символов будет "abc", поскольку все символы в ней уникальны.

Таким образом, задача требует написать функцию, которая будет принимать строку в качестве входных данных и возвращать длину самой длинной подстроки без повторяющихся символов.

Как решать задачу

Для решения этой задачи можно использовать различные методы, в том числе:

Брутфорс Это самый простой метод, который проверяет каждую подстроку на наличие повторяющихся символов. Однако, этот метод не эффективен, так как он имеет сложность O(n^3).
Слайд окно Этот метод использует два указателя, которые двигаются по строке. Если текущий символ не встречался ранее, то он добавляется в множество уникальных символов и правый указатель сдвигается. Если символ встречался, то левый указатель сдвигается. Этот метод эффективен и имеет сложность O(n).
Оптимизация словаря. Этот метод использует словарь для хранения последнего встречаемого символа. Если символ встречается повторно, то левый указатель сдвигается на позицию следующего символа после предыдущего вхождения символа. Этот метод также эффективен и имеет сложность O(n).
Динамическое программирование. Этот метод использует массив для хранения длин самой длинной подстроки без повторяющихся символов, который обновляется на каждом шаге. Этот метод может быть более сложным, чем другие методы, но он может быть более эффективным, если есть ограничения на размер строки.

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

# README