Овладейте искусством поиска самой длинной подстроки без повторяющихся символов в JavaScript. #CodingInterviews #JavaScriptAlgorithms
Во время интервью по кодированию и в реальных сценариях часто возникают проблемы, требующие поиска шаблонов или последовательностей в заданной строке. Одной из таких задач является нахождение длины самой длинной подстроки без повторяющихся символов. В этой статье мы рассмотрим концепцию поиска самой длинной подстроки без повторяющихся символов и предложим эффективный алгоритмический подход к решению этой проблемы с помощью JavaScript. Мы также включим реализацию кода с подробными пояснениями и предоставим пример для иллюстрации решения.
Постановка задачи:
Наша цель — найти длину самой длинной подстроки, не содержащей повторяющихся символов. Например, в строке «abcabcbb» самой длинной подстрокой без повторяющихся символов является «abc» длиной 3.
Алгоритмический подход:
Чтобы эффективно решить эту проблему, мы можем использовать подход скользящего окна с помощью множества. Алгоритмический подход можно резюмировать следующим образом:
- Инициализируйте два указателя, левый и правый, для отслеживания границ окна подстроки.
- Инициализируйте набор, чтобы отслеживать уникальные символы в текущем окне.
- Инициализируйте переменную maxLength для хранения длины самой длинной подстроки без повторяющихся символов.
- Переместите правый указатель, чтобы расширить окно, пока не будет найден повторяющийся символ или не будет достигнут конец строки.
- Если обнаружен повторяющийся символ, переместите левый указатель вправо, чтобы уменьшить окно и удалить повторяющийся символ из набора.
- Обновите maxLength, если текущая длина окна больше, чем предыдущая maxLength.
- Повторяйте шаги 4–6, пока правый указатель не достигнет конца строки.
- Верните maxLength в качестве результата.
Реализация кода в JavaScript:
const findLongestSubstring = (str) => { let left = 0; let right = 0; let maxLength = 0; const charSet = new Set(); while (right < str.length) { if (!charSet.has(str[right])) { charSet.add(str[right]); maxLength = Math.max(maxLength, charSet.size); right++; } else { charSet.delete(str[left]); left++; } } return maxLength; }; // Example usage const inputString = "abcabcbb"; const lengthOfLongestSubstring = findLongestSubstring(inputString); console.log(lengthOfLongestSubstring); // Output: 3
Объяснение:
- Мы инициализируем левый и правый указатели на 0, представляя начало и конец окна соответственно.
- Мы также инициализируем maxLength равным 0 и создаем пустой набор с именем charSet для хранения уникальных символов.
- Используя цикл while, мы перебираем строку, пока правый указатель не достигнет конца.
- Внутри цикла мы проверяем, не присутствует ли символ в правом указателе в charSet.
- Если его нет, мы добавляем символ в набор, при необходимости обновляем maxLength и перемещаем правый указатель на следующую позицию.
- Если он уже присутствует, значит, мы столкнулись с повторяющимся символом. В этом случае мы удаляем символ слева от указателя из набора и перемещаем левый указатель вправо, чтобы сжать окно.
- Мы повторяем шаги 4 и 5, пока правый указатель не достигнет конца строки, гарантируя, что мы покрываем все возможные подстроки.
- Наконец, мы возвращаем maxLength, представляющую длину самой длинной подстроки без повторяющихся символов.
Краткое содержание:
Проблема нахождения длины самой длинной подстроки без повторяющихся символов может быть эффективно решена с использованием техники скользящего окна и заданной структуры данных в JavaScript. Поддерживая два указателя и набор для отслеживания уникальных символов в текущем окне, мы можем найти длину самой длинной подстроки без повторяющихся символов. Этот алгоритм имеет временную сложность O(n), так как мы обходим строку только один раз. Понимание и реализация этого подхода поможет вам эффективно решать аналогичные проблемы при кодировании интервью и реальных сценариев.
Надеюсь, что приведенная выше статья дала лучшее понимание. Если у вас есть какие-либо вопросы относительно областей, которые я обсуждал в этой статье, области улучшения, не стесняйтесь комментировать ниже.
[Раскрытие информации: эта статья является совместным творением, в котором мои собственные идеи сочетаются с помощью ChatGPT для оптимальной артикуляции.]