LeetCode 3 - Longest Substring Without Repeating Characters (Medium)

문제

LeetCode - 3번

풀이 과정

중복된 문자가 없는 부분 문자열 중에서 가장 길이가 긴 것을 찾는 문제입니다.

두 개의 포인터 head, tail 를 활용해서 윈도우를 나타내고 중복된 문자가 발견되면
현재 윈도우에서 중복된 문자의 위치로 head 를 이동시키면 됩니다.

코드

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const cache = new Map();
  let head = 0;
  let tail = 0;
  let answer = 0;

  for (; tail < s.length; tail++) {
    if (cache.has(s[tail])) {
      const duplicateIndex = cache.get(s[tail]);

      for (let i = head; i < duplicateIndex; i++) {
        cache.delete(s[i]);
      }

      answer = Math.max(answer, tail - head);
      head = duplicateIndex + 1;
    }

    cache.set(s[tail], tail);
  }

  answer = Math.max(answer, tail - head);

  return answer;
};