Овладейте искусством поиска самой длинной подстроки без повторяющихся символов в JavaScript. #CodingInterviews #JavaScriptAlgorithms

Во время интервью по кодированию и в реальных сценариях часто возникают проблемы, требующие поиска шаблонов или последовательностей в заданной строке. Одной из таких задач является нахождение длины самой длинной подстроки без повторяющихся символов. В этой статье мы рассмотрим концепцию поиска самой длинной подстроки без повторяющихся символов и предложим эффективный алгоритмический подход к решению этой проблемы с помощью JavaScript. Мы также включим реализацию кода с подробными пояснениями и предоставим пример для иллюстрации решения.

Постановка задачи:

Наша цель — найти длину самой длинной подстроки, не содержащей повторяющихся символов. Например, в строке «abcabcbb» самой длинной подстрокой без повторяющихся символов является «abc» длиной 3.

Алгоритмический подход:

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

  1. Инициализируйте два указателя, левый и правый, для отслеживания границ окна подстроки.
  2. Инициализируйте набор, чтобы отслеживать уникальные символы в текущем окне.
  3. Инициализируйте переменную maxLength для хранения длины самой длинной подстроки без повторяющихся символов.
  4. Переместите правый указатель, чтобы расширить окно, пока не будет найден повторяющийся символ или не будет достигнут конец строки.
  5. Если обнаружен повторяющийся символ, переместите левый указатель вправо, чтобы уменьшить окно и удалить повторяющийся символ из набора.
  6. Обновите maxLength, если текущая длина окна больше, чем предыдущая maxLength.
  7. Повторяйте шаги 4–6, пока правый указатель не достигнет конца строки.
  8. Верните 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

Объяснение:

  1. Мы инициализируем левый и правый указатели на 0, представляя начало и конец окна соответственно.
  2. Мы также инициализируем maxLength равным 0 и создаем пустой набор с именем charSet для хранения уникальных символов.
  3. Используя цикл while, мы перебираем строку, пока правый указатель не достигнет конца.
  4. Внутри цикла мы проверяем, не присутствует ли символ в правом указателе в charSet.
  5. Если его нет, мы добавляем символ в набор, при необходимости обновляем maxLength и перемещаем правый указатель на следующую позицию.
  6. Если он уже присутствует, значит, мы столкнулись с повторяющимся символом. В этом случае мы удаляем символ слева от указателя из набора и перемещаем левый указатель вправо, чтобы сжать окно.
  7. Мы повторяем шаги 4 и 5, пока правый указатель не достигнет конца строки, гарантируя, что мы покрываем все возможные подстроки.
  8. Наконец, мы возвращаем maxLength, представляющую длину самой длинной подстроки без повторяющихся символов.

Краткое содержание:

Проблема нахождения длины самой длинной подстроки без повторяющихся символов может быть эффективно решена с использованием техники скользящего окна и заданной структуры данных в JavaScript. Поддерживая два указателя и набор для отслеживания уникальных символов в текущем окне, мы можем найти длину самой длинной подстроки без повторяющихся символов. Этот алгоритм имеет временную сложность O(n), так как мы обходим строку только один раз. Понимание и реализация этого подхода поможет вам эффективно решать аналогичные проблемы при кодировании интервью и реальных сценариев.

Надеюсь, что приведенная выше статья дала лучшее понимание. Если у вас есть какие-либо вопросы относительно областей, которые я обсуждал в этой статье, области улучшения, не стесняйтесь комментировать ниже.

[Раскрытие информации: эта статья является совместным творением, в котором мои собственные идеи сочетаются с помощью ChatGPT для оптимальной артикуляции.]