[LeetCode] Top Interview Problems 3. Longest Substring Without Repeating Characters - JavaScript

🔗 문제 링크

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

✏️ 풀이

var lengthOfLongestSubstring = function(s) {
  if (!s.length) {
    return 0;
  }
  
  const map = new Map();
  let start = 0;
  let maxLength = 0;

  for (let i = 0; i < s.length; i++) {
    const letter = s[i];
    if (map.has(letter)) {
      const nextStart = map.get(letter);
      for (let i = start; i < nextStart; i++) {
          map.delete(s[i]);
      }
      start = nextStart;
    }
    map.set(letter, i + 1);
    maxLength = Math.max(maxLength, i - start + 1);
  }
    
  return maxLength;
};

문자열 s를 순회하면서 인덱스가 start부터 i까지인 substring의 길이를 maxLength와 비교하여 maxLength를 계속 최댓값으로 갱신하였다. 만약 i번째 글자가 현재 substring에 포함되지 않은 글자라면 map에 기록하고, 만약 이미 포함된 글자라면 이전에 map에 기록된 index 이전까지의 모든 글자들을 삭제한다. 이렇게 해서 매번 substring이 중복되지 않은 글자를 갖도록 하였다.