Как найти самую длинную подстроку без повторяющихся символов
3 февраля 2023 г.Описание задачи:
По заданной строке s найдите длину самой длинной подстроки без повторяющихся символов.
Ограничения:
0 <= s.length <= 5 * 10^4sсостоит из английских букв, цифр, символов и пробелов.
Пример 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 и начинаем заново.
Это простой, но неэффективный подход.
Сложность:
- Временная сложность:
O(n*n) - Пространственная сложность:
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 шаг, как только встречаем дубликат и начинаем все сначала. Мы будем перемещать левую границу до тех пор, пока существует дубликат.
Сложность:
- Временная сложность:
O(n) - Пространственная сложность:
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().
Приведенный выше алгоритм дает нам следующий результат.
Я надеюсь, что эта статья помогла вам понять, как решить проблему такого типа. Буду рад вашим отзывам.
До скорой встречи! ✌
Оригинал