DEV Community

faangmaster
faangmaster

Posted on • Updated on

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

Задача.

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

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

Image description

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

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

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

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

Enter fullscreen mode Exit fullscreen mode

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

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

Enter fullscreen mode Exit fullscreen mode

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

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);
}

Enter fullscreen mode Exit fullscreen mode

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

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;
}
Enter fullscreen mode Exit fullscreen mode

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

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

Map<Character, Integer> slidingWindow = new HashMap<>();
Enter fullscreen mode Exit fullscreen mode

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

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;
}

Enter fullscreen mode Exit fullscreen mode

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

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

Вместо удаления элементов из скользящего окна мы можем просто переместить 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;
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (1)

Collapse
 
idsulik profile image
Suleiman Dibirov

Хорошее объяснение, наглядное!
Недавно записывал видео с объяснением этой задачи, но с использованием hashmap youtube.com/watch?v=I7anzFVj0pM