Разбор задачи 3. Longest Substring Without Repeating Characters LeetCode.com

3 . Самая длинная подстрока без повторяющихся символов

Дана строка s, найдите длину самой длинной 

подстрокабез повторяющихся символов.

Пример 1:

Ввод: s = "abcabcbb"
 Вывод: 3
 Объяснение: Ответ "abc", длина 3.

Пример 2:

Вход: s = "bbbb"
 Выход: 1
 Объяснение: Ответ "b" с длиной 1.

Пример 3:

Ввод: s = "pwwkew"
 Вывод: 3
 Объяснение: Ответ "wke" с длиной 3.
Обратите внимание, что ответ должен быть подстрокой, «pwke» — это подпоследовательность, а не подстрока.

Ограничения:
0 <= s.length <= 5 * 104
sсостоит из английских букв, цифр, символов и пробелов.

Для решения этой задачи можно использовать алгоритм «скользящего окна» (sliding window). Он заключается в том, чтобы определять длину самой длинной подстроки без повторяющихся символов, начиная с каждого символа строки. Таким образом, мы будем поочередно рассматривать все возможные подстроки и выбирать из них наибольшую.

Алгоритм будет использовать два указателя, left и right, которые будут представлять левую и правую границы текущей подстроки. Начальное значение обоих указателей будет равно 0. Мы также будем использовать словарь seen, который будет хранить информацию о том, какие символы уже были встречены в текущей подстроке. Если мы встречаем символ, который уже есть в словаре seen, мы сдвигаем левую границу left до следующего после встреченного символа, чтобы исключить его из текущей подстроки.

Кроме того, мы будем поддерживать переменную max_length, которая будет хранить длину наибольшей найденной подстроки без повторяющихся символов.

Решение задачи «Самая длинная подстрока без повторяющихся символов» пример кода на Python

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        # Получаем длину строки
        n = len(s)
        # Создаем множество для хранения уникальных символов в текущей подстроке
        char_set = set()
        # Инициализируем переменные для ответа, начала и конца текущей подстроки
        ans, i, j = 0, 0, 0
        # Итерируемся по строке, пока не достигнем конца строки
        while i < n and j < n:
            # Если текущий символ еще не встречался в текущей подстроке
            if s[j] not in char_set:
                # Добавляем его в множество уникальных символов
                char_set.add(s[j])
                # Увеличиваем конец текущей подстроки
                j += 1
                # Обновляем ответ, если текущая подстрока больше предыдущей
                ans = max(ans, j - i)
            # Если текущий символ уже был в текущей подстроке
            else:
                # Удаляем первый символ из текущей подстроки
                char_set.remove(s[i])
                # Увеличиваем начало текущей подстроки
                i += 1
        # Возвращаем длину самой длинной подстроки без повторяющихся символов
        return ans

Решение задачи «Самая длинная подстрока без повторяющихся символов» пример кода на Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Получаем длину строки
        int n = s.length();
        // Создаем множество для хранения уникальных символов в текущей подстроке
        Set<Character> set = new HashSet<>();
        // Инициализируем переменные для ответа, начала и конца текущей подстроки
        int ans = 0, i = 0, j = 0;
        // Итерируемся по строке, пока не достигнем конца строки
        while (i < n && j < n) {
            // Если текущий символ еще не встречался в текущей подстроке
            if (!set.contains(s.charAt(j))) {
                // Добавляем его в множество уникальных символов
                set.add(s.charAt(j++));
                // Обновляем ответ, если текущая подстрока больше предыдущей
                ans = Math.max(ans, j - i);
            // Если текущий символ уже был в текущей подстроке
            } else {
                // Удаляем первый символ из текущей подстроки
                set.remove(s.charAt(i++));
            }
        }
        // Возвращаем длину самой длинной подстроки без повторяющихся символов
        return ans;


    }
}

Решение задачи «Самая длинная подстрока без повторяющихся символов» пример кода на C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Создаем unordered_map для хранения индексов символов в строке
        unordered_map<char, int> seen;
        // Инициализируем начало текущей подстроки и максимальную длину подстроки
        int left = 0;
        int maxLength = 0;
        
        // Итерируемся по строке, двигая правый указатель
        for (int right = 0; right < s.length(); right++) {
            // Если символ уже встречался в подстроке и его последнее вхождение находится правее начала текущей подстроки
            if (seen.count(s[right]) && seen[s[right]] >= left) {
                // Сдвигаем начало текущей подстроки на следующий символ после последнего вхождения текущего символа
                left = seen[s[right]] + 1;
            }
            // Обновляем индекс текущего символа в unordered_map
            seen[s[right]] = right;
            // Обновляем максимальную длину подстроки, если текущая подстрока больше предыдущей
            maxLength = max(maxLength, right - left + 1);
        }
        
        // Возвращаем длину самой длинной подстроки без повторяющихся символов
        return maxLength;
    }
};

Решение задачи «Самая длинная подстрока без повторяющихся символов» пример кода на JavaScript

var lengthOfLongestSubstring = function(s) {
    // Получаем длину строки и инициализируем переменные
    let n = s.length, ans = 0;
    let set = new Set();
    let i = 0, j = 0;
    // Итерируемся по строке, двигая указатели
    while (i < n && j < n) {
        // Если символ не встречался ранее, добавляем его в множество и сдвигаем правый указатель
        if (!set.has(s[j])) {
            set.add(s[j++]);
            ans = Math.max(ans, j - i);
        } else {
            // Если символ уже был в множестве, удаляем первый символ из текущей подстроки и сдвигаем левый указатель
            set.delete(s[i++]);
        }
    }
    // Возвращаем длину самой длинной подстроки без повторяющихся символов
    return ans;
};

Решение задачи «Самая длинная подстрока без повторяющихся символов» пример кода на C#

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        // Получаем длину строки и инициализируем переменные
        int n = s.Length, ans = 0;
        HashSet<char> set = new HashSet<char>();
        int i = 0, j = 0;
        // Итерируемся по строке, двигая указатели
        while (i < n && j < n) {
            // Если символ не встречался ранее, добавляем его в множество и сдвигаем правый указатель
            if (!set.Contains(s[j])) {
                set.Add(s[j++]);
                ans = Math.Max(ans, j - i);
            } else {
                // Если символ уже был в множестве, удаляем первый символ из текущей подстроки и сдвигаем левый указатель
                set.Remove(s[i++]);
            }
        }
        // Возвращаем длину самой длинной подстроки без повторяющихся символов
        return ans;
    }
}