[알고리즘] LeetCode 3. Longest Substring Without Repeating Characters JS

개요

문자열이 주어질 때, 문자열 내부에서 중복없이 이어지는 문자열 중,  가장 긴 문자열의 길이를 리턴하는 문제이다.

 

Longest Substring Without Repeating Characters - LeetCode

 

풀이

문자열 문제를 많이 안풀어봐서 조금 헷갈렸다. 그래도 기본적인 슬라이딩 윈도우를 사용한다는 것은 문자열 문제들 중 많이 출제되는 유형인거 같아 나름 쉽게 눈치 챌 수 있었다.

 

여기에 해쉬를 사용해 현재 문자열 정보를 가지고 있다가 중복이 없어야하니 해쉬에 값이 2가 넘어가는 문자가 나올 때 중복되는 문자를 없애기 위해 계속해서 lt를 증가시켰다.

 

그렇게 배열에 끝까지 돌리면 된다

/**
 * @param {string} s
 * @return {number}
 *
 * 문자열이 주어질 때
 * 연결되는 문자열 중에서 반복되는 문자없이 가장 긴 문자열을 반환해라
 */
var lengthOfLongestSubstring = function (s) {
  const map = new Map();
  let max = 0;
  let lt = 0;
  for (let rt = 0; rt < s.length; rt++) {
    const char = s[rt];
    map.set(char, (map.get(char) || 0) + 1);
    if (map.get(char) > 1) {
      while (map.get(char) !== 1) {
        map.set(s[lt], map.get(s[lt]) - 1);
        lt++;
      }
    }
    max = Math.max(rt - lt + 1, max);
  }
  return max;
};