Comments 16
Если ставите минус, то большая просьба отписаться, чтобы я знал что не так и мог исправить)
Я всегда рад аргументированной критике
Это просто хабр, сюда заходят желчью побрызгать😄
Ты: стараешься, разбираешься, статью пишешь...
Комментаторы: БАЯН! ЗАБАНИТЬ! НИЧТОЖЕСТВО!
К сожалению, есть такое, весь спектр ощутил после первой статьи https://habr.com/ru/articles/786184/
Но в то же время бывают и полезные комментарии, поэтому натягиваем броню и вперед)
Тут такая же критика, как и к другой статье: объяснения не должны повторять код. Не показаны идеи и суть решения.
Например, раз уж вы начали про окно, можно объяснять так:
Скользящее окно: мы будем поддерживать самый длинный отрезок, который хороший и заканчивается в текущей правой позиции. Будем двигать эту позицию и пересчитывать левую. Ясно*, что левая граница при таком подходе будет двигаться только вправо. Теперь нам осталось научится быстро сдвигать левую границу. Можно двигать ее по одному символу, пока окно не станет хорошим. Осталось быстро научиться понимать, хорошее ли у нас окно. Это можно сделать считая, сколько каждых букв у нас есть в окне. Вот таким вот счетчиком/хеш-таблицей. Суммарно левая граница сдвинется максимум n раз, поэтому все решение будет O(n).
Прийти к этому можно вот так:
Описали наивное решение, которое для каждого начала двигает конец, пока не встретит повтор. Улучшение: при сдвиге левой границы правая в конце будет не хуже. Т.е. можно начинать уже с того же самого места, но тут надо поддерживать счетчик между итерациями. Потом можно сказать, что неважно, какую из границ перебирать, а какую корректировать под первую. Можно перебирать правую границу, а сдвигать левую. Но так код легче - ибо надо будет сдвигать только пока окно плохое, а не надо будет смотреть наперед.
Спасибо за обратную связь!
Дважды перечитал, но к сожалению такое объяснение даже мне было трудно понимать, хотя я знаю как этот механизм работает.
Но в целом я понял, что нужно поменять подход для текстовых объяснений.
Буду рад, если получу подобный фидбек для видео)
В видео тоже самое. Можно во время объяснения еще и рисовать эти окна. Вы там что-то рисуете, но идею решения, опять же, не объясняете.
я же там как раз рисую окошко и двигаю его на каждом шаге, объясняя почему двигаю с левой стороны(то есть сужаю) или двигаю с правой стороны.
Опять же, вы объясняете что там происходит, а не почему. Да, окошко сужается. Да, потому что в окне не должно быть повторяющих символов. Но почему это находит ответ?
Как буду перезаписывать, я бы объяснил, что это помогает не делать одни и те же операции раз за разом, то есть убираем дублирующие операции, я на каком-то видео наглядно объяснял, почему sliding window работает лучше, чем брутфорс, но к сожалению на этом видео не так хорошо получилось это объяснить.
Спасибо за фидбек!
А что будет со строкой "paww"?
Вместо множества, можно использовать хэш-таблицу с последними встреченными индексами для символов, чтобы сразу переставлять левый край окна, если встретился повтор. Вот моё решение:
var lengthOfLongestSubstring = function(s) {
const lastIndexes = new Map(); // хэштаблица (карта "ключ-значение")
let maxLen = 0;
let start = -1; // левый край окна
for (let i = 0; i < s.length; ++i) {
const char = s.charCodeAt(i); // текущий символ в строке
const lastPos = lastIndexes.get(char) ?? -1; // -1, если не нашлось в карте
lastIndexes.set(char, i);
start = Math.max(start, lastPos);
maxLen = Math.max(maxLen, i - start);
}
return maxLen;
};
По-моему задачка уровня easy с литкода. Хотелось бы видеть решения medium-hard задачек, а то на этих собес точно никуда не пройдешь)
Это medium задача https://leetcode.com/problems/longest-substring-without-repeating-characters , которую дают в десятки разных компаний, включая FAANG)
Решение задачи с собеседования Longest Substring Without Repeating Characters [+ ВИДЕО]