Как найти самую длинную подстроку без повторяющихся символов
leetcode data-structures java

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

3 февраля 2023 г.

Описание задачи:

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

Ограничения:

  • 0 <= s.length <= 5 * 10^4
  • s состоит из английских букв, цифр, символов и пробелов.

Пример 1:

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

Пример 2:

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

Пример 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.

Грубая сила

Идея проста: мы исправляем одну букву и перебираем остальную часть строки, пока не встретим дубликат. Сохраняем все буквы в наборе, и как только находим повторяющуюся букву, сдвигаем левую границу на 1 и начинаем заново.

Это простой, но неэффективный подход.

Сложность:

  1. Временная сложность: O(n*n)
  2. Пространственная сложность: O(n)

public int lengthOfLongestSubstring(String s) {
    int max = 0;
    for (int left=0; left<s.length(); stleftart++) {
        Set<Character> set = new HashSet<>();
        for (int right=left; right<s.length(); right++) {
            if (left != right && set.contains(s.charAt(right))) {
                break;
            }
            set.add(s.charAt(right));
         }
         max = Math.max(max, set.size());
    }
    return max;
}

Оптимизированный подход

Идея оптимизации заключается в том, что мы не хотим делать только 1 шаг, как только встречаем дубликат и начинаем все сначала. Мы будем перемещать левую границу до тех пор, пока существует дубликат.

Сложность:

  1. Временная сложность: O(n)
  2. Пространственная сложность: O(n)

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int max = 0;
    for (int i=0; i<s.length(); i++) {
         char c = s.charAt(i);
        if (set.contains(c)) {
            while (c != s.charAt(i - set.size())) {
                set.remove(s.charAt(i - set.size()));
            }
        } else {
            set.add(c);
        }
        if (set.size() > max) max = set.size();
    }
    return max;
}

Хочу отметить, что я не сохраняю левую границу в отдельную переменную (хотя это возможно).

Поскольку левая граница нужна только тогда, когда мы сталкиваемся с дубликатом, поэтому я точно знаю, сколько уникальных символов было: set.size().

Следовательно, я могу найти левую границу по формуле: i - set.size().

Приведенный выше алгоритм дает нам следующий результат.

Я надеюсь, что эта статья помогла вам понять, как решить проблему такого типа. Буду рад вашим отзывам.

До скорой встречи! ✌

Оригинал

Recent Post

Categories

PREVIOUS ARTICLE
NEXT ARTICLE