Найдовша послідовність символів без повторень · fullstack.org.ua

Найдовша послідовність символів без повторень

ПросунутийJavaScript

Знайдіть довжину найдовшої підпослідовності рядка без символів, що повторюються.

Напишіть функцію solve(str), яка повертає довжину найдовшої неперервної підпослідовності символів рядка str, у якій жоден символ не повторюється.

Приклади

Вхід: "abcabcbb"

Вихід: 3

найдовша — "abc"

Вхід: "bbbbb"

Вихід: 1

найдовша — один символ "b"

Вхід: "pwwkew"

Вихід: 3

найдовша — "wke"

Обмеження: 0 ≤ str.length ≤ 1000

Ваше рішення

Підказки

Підказка 1

Це задача на ковзне вікно (sliding window): тримайте початок поточної підпослідовності без повторень і рухайте кінець по рядку.

Підказка 2

Map, що зберігає останню позицію кожного символу, дозволяє за O(1) визначити, чи символ уже є у поточному вікні, і швидко посунути початок вікна одразу за його попереднім входженням.

Пояснення розв'язку

javascript

function solve(str) {
  let maxLen = 0;
  let start = 0;
  const seen = new Map();

  for (let end = 0; end < str.length; end++) {
    const char = str[end];
    if (seen.has(char) && seen.get(char) >= start) {
      start = seen.get(char) + 1;
    }
    seen.set(char, end);
    maxLen = Math.max(maxLen, end - start + 1);
  }

  return maxLen;
}