faangmaster

Posted on Jul 23 • Edited on Jul 30

Задача с собеседования в Microsoft: Наибольшая подстрока без повторяющихся символов.

#interview #faang #microsoft #algorithms

Задача.

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

Пример 1:

Input: s = "abcabcbb"
Output: 3
Наибольшая подстрока без повторяющихся символов: "abc"

Пример 2:

Input: s = "bbbbb"
Output: 1

Input: s = "pwwkew"
Output: 3
Наибольшая подстрока без повторяющихся символов: "wke"

Ссылка на leetcode: https://leetcode.com/problems/longest-substring-without-repeating-characters

Решение.

Для решения можно использовать SlidingWindow (скользящее окно). Для этого пройдем циклом по строке, в скользящем окне будем хранить предыдущие символы строки, пока они уникальны. Как только мы встретим повторяющийся элемент, нам нужно сократить размер скользящего окна до размера, когда оно снова будет хранить только уникальные символы.
Давайте посмотрим на примере строки s = "pwwkew".

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

Вначале right = 0, символ по этому индексу - "p". В скользящем окне у нас ничего нет. Т.к. все символы там уникальны, то добавим символ "p" в скользящее окно и увеличим индекс right на единицу:

Для right = 1, символ строки - "w". В скользящем окне у нас только символ "p". Если мы туда добавим символ "w", то там будут только уникальные символы. Поэтому добавляем "w" в скользящее окно и увеличиваем right на единицу:

Теперь right = 2, символ строки - "w". Такой символ у нас уже есть в скользящем окне. Поэтому, когда мы снова добавим "w" в скользящее окно, то у нас будут повторяющиеся элементы. Чтобы сделать все элементы в скользящем окне уникальными, нам надо из него удалять элементы слева до тех пор, пока мы не удалим символ "w". Для этого пройдем циклом по скользящему окну слева направо и будем удалять элементы до тех пор, пока в нем не будет "w". Обозначим текущий индекс этого цикла как left.

left = 0, удалим символ "p" из скользящего окна:

left = 1, скользящее окно все еще содержит символ "w". Удалим следующий символ:

left = 2. Скользящее окно теперь пустое. В нем снова все элементы уникальны. Поэтому завершим этот цикл и добавим в скользящее окно символ по индексу right и увеличим right на единицу:

right = 3, символ "k". Если мы добавим его в скользящее окно - в нем все еще будут только уникальные элементы. Поэтому добавляем "k" в скользящее окно и увеливаем right на единицу:

Аналогично для right = 4:

Для right = 5, символ строки - "w". Такой символ уже есть в скользящем окне. Поэтому повторим снова цикл по скользящему окну. Будем удалять из него элементы слева направо, до тех пор, пока в нем не останется символа "w":

После этого добавим "w" в скользящее окно и увеличим right на единицу:

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

Преобразуем это в код.

Цикл по строке:

for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    ...
}

Используем в качестве SlidingWindow - Set:

Set<Character> slidingWindow = new HashSet<>();
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    ...
    //Добавление в скользящее окно
    slidingWindow.add(c);
}

Добавим вложенный цикл по скользящему окну для удаления символов слева направо, пока не удалим текущий символ, если он уже встретился:

Set<Character> slidingWindow = new HashSet<>();
int left = 0
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    while (slidingWindow.contains(c)) {
        slidingWindow.remove(s.charAt(left));
        left++;
    }
    //Добавление в скользящее окно
    slidingWindow.add(c);
}

И наконец, добавим трекинг текущего размера скользящего окна и максимального:

public int lengthOfLongestSubstring(String s) {
    Set<Character> slidingWindow = new HashSet<>();
    int left = 0;
    int maxLength = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (slidingWindow.contains(c)) {
            slidingWindow.remove(s.charAt(left));
            left++;
        }
        slidingWindow.add(c);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Временная сложность - O(2N) -> O(N). Двойка берется из того, что у нас есть вложенный цикл. Но в худщем случае, в сумме, он сделает N итераций за все время работы алгоритма.
Сложность по памяти - O(k). k - число уникальных символом. Если в строке только англиские буквы, то k = 26.

Можно ли улучшить это решение? Можно убрать вложенный цикл и сократить число итераций в два раза. Для этого вместо Set будем использовать Map. Он также будет содержать предыдущие символы строки, но еще он будет хранить индекс символа в строке, когда мы его встречали в предыдущий раз, чтобы можно было переместить left на нужную позицию сразу без цикла.
Создаем SlidingWindow в виде hashmap:

Map<Character, Integer> slidingWindow = new HashMap<>();

Все остальное остается точно также, кроме внутреннего цикла:

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> slidingWindow = new HashMap<>();
    int left = 0;
    int maxLength = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        .... //Тут надо перевычислить left
        slidingWindow.put(c, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Теперь мы сразу можем перевычислись left без итераций следующим образом:

if (slidingWindow.containsKey(c)) {
    left = Math.max(slidingWindow.get(c) + 1, left);
}

Вместо удаления элементов из скользящего окна мы можем просто переместить left на slidingWindow.get(c) + 1 - следующий индекс после того, когда мы последний раз видели наш повторяющийся элемент.
Максимум нам нужно взять, т.к. мы не удаляем никакие символы из нашей мапы и у нас могут быть случаи, когда наш элемент повторялся на позиции меньше текущего значения left.
Все вместе:

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> slidingWindow = new HashMap<>();
    int left = 0;
    int maxLength = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (slidingWindow.containsKey(c)) {
            left = Math.max(slidingWindow.get(c) + 1, left);
        }
        slidingWindow.put(c, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Временная сложность такого решения - O(N).
Сложность по памяти - O(k), где k - число уникальных элементов в строке. Т.к. мы храним все элементы строки в мапе, то в худшем случае, число ключей в мапе будет равно числу уникальных элементов в строке.