Ссылка на видео:
Ответы на вопросы
Решение алгоритмической задачи
Условия задачи:
Given a string s, find the length of the longest substring without repeating characters.
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 * 10^4
s consists of English letters, digits, symbols and spaces.Для решения этой задачи можно использовать метод двух указателей (two pointers approach) с использованием HashMap. Алгоритм работает следующим образом:
- Инициализируем два указателя left и right, которые будут указывать на начало и конец текущей подстроки. Переменная maxLength будет использоваться для отслеживания максимальной длины подстроки без повторяющихся символов.
- Создаем HashMap, где ключом будет символ из строки s, а значением – его индекс в строке s.
- Пока правый указатель не достигнет конца строки s:a. Если символ, на который указывает правый указатель, уже находится в HashMap и его индекс больше или равен левому указателю, значит мы нашли повторяющийся символ. Тогда необходимо обновить левый указатель на следующий индекс после повторяющегося символа.b. Добавляем символ и его индекс в HashMap.c. Обновляем maxLength, если текущая длина подстроки без повторяющихся символов больше предыдущей maxLength.
- Возвращаем maxLength.
Код на Java будет выглядеть следующим образом:
import java.util.*;
public class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int left = 0;
int right = 0;
Map<Character, Integer> map = new HashMap<>();
while (right < s.length()) {
char c = s.charAt(right);
if (map.containsKey(c) && map.get(c) >= left) {
left = map.get(c) + 1;
}
map.put(c, right);
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
}Мы создали метод lengthOfLongestSubstring, который принимает строку s и возвращает длину наибольшей подстроки без повторяющихся символов.
Внутри метода мы инициализировали переменные maxLength, left, right и создали HashMap map.
Затем мы запускаем цикл, который продолжается до тех пор, пока правый указатель right не достигнет конца строки s.
В цикле мы проверяем, содержит ли HashMap символ, на который указывает правый указатель. Если символ уже есть в HashMap и его индекс больше или равен левому указателю left, то мы нашли повторяющийся символ. В этом случае мы обновляем левый указатель left на следующий индекс после повторяющегося символа.
Затем мы добавляем текущий символ и его индекс в HashMap. Обновляем maxLength, если текущая длина подстроки без повторяющихся символов больше предыдущей maxLength. И, наконец, увеличиваем правый указатель на единицу и повторяем процесс, пока правый указатель не достигнет конца строки s.
После того как цикл завершится, мы возвращаем переменную maxLength, которая содержит длину наибольшей подстроки без повторяющихся символов.
Например, если мы передадим строку “abcabcbb” в метод lengthOfLongestSubstring, то он вернет значение 3, что соответствует длине подстроки “abc”, которая является наибольшей подстрокой без повторяющихся символов.
Аналогично, если мы передадим строку “bbbbb”, то метод вернет значение 1, так как в данной строке все символы повторяются, а значит длина наибольшей подстроки без повторяющихся символов равна 1.
И, наконец, если мы передадим строку “pwwkew”, то метод вернет значение 3, так как наибольшая подстрока без повторяющихся символов в этой строке – “wke”, длина которой равна 3.
Таким образом, метод lengthOfLongestSubstring позволяет найти длину наибольшей подстроки без повторяющихся символов в заданной строке s, используя метод двух указателей и HashMap.
Системный дизайн YouTube
Детальный разбор построения системного дизайна YouTube и похожих сервисов приведен в статье по этой ссылке