📌 문제 설명

Longest Substring Without Repeating Characters 문제 보기

📌 문제 접근

처음에 O(N) 정도의 속도를 내기 위하여, 두 포인터를 활용하자는 생각을 하였다. 그런데 end는 그냥 계속 이동하고 start만 갱신하면 된다고 생각하였다. 그래서 슬라이딩 윈도우를 사용하여 작성하였다. 어려운 점은 없는 문제.

📌 내가 작성한 코드

/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = (s) => {
  const map = new Map();
  let [start, len] = [0, 0];
  for (let i = 0; i < s.length; i++) {
    end = i;
    if (map.has(s[i])) start = Math.max(start, map.get(s[i]) + 1);
    map.set(s[i], i);
    len = Math.max(len, i - start + 1);
  }
  return len;
};

📌 시간 복잡도

O(N) - 문자열을 한 번 순회하며 각 문자는 상수 시간에 처리되므로 (N: 문자열 길이)

📌 참고 링크

• Array.prototype.map() - MDN
• Sliding Window Protocol - 위키백과