3. Longest Substring Without Repeating Characters

💡 풀이

var lengthOfLongestSubstring = function (s) {
  if (!s) return 0;

  let map = new Map();
  for (let i = 0; i < s.length; i++) map.set(s[i], -1);

  let max = 0;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) start = Math.max(start, map.get(s[i]) + 1);

    map.set(s[i], i);
    max = Math.max(max, i - start + 1);
  }
  //   console.table(map);
  //   console.log('max: ', max);

  return max;
};

let s = 'abcabcbb';
lengthOfLongestSubstring(s);

📝 정리

• 유사 문제: https://velog.io/@ken1204/724.-Find-Pivot-Index

• Sliding Window 알고리즘 참고 링크: https://m.blog.naver.com/kks227/220795165570

문제는 중복되는 문자가 없는 가장 긴 subString을 찾는 것이다.

Two pointers를 사용한 풀이다. 전에 살펴봤던 Sliding Window 알고리즘을 이용해 유사하게 풀었다. 풀이 순서는 다음과 같다.

• 먼저 s에 있는 알파벳마다 -1을 value값으로 가지는 map을 만들어준다.

• 이후 start 인덱스와 i(=end)인덱스를 만들어준다.

• 이후 map.set()을 이용해 key는 s[i], value는 i로 map을 채워준다.

• 이후 map 안에 key로 s[i]가 있는지 확인하고(중복 확인), 있다면 start 포인터를 중복됐던 요소보다 한 칸 앞으로 배치해준다. 만약 start 포인터가 중복 요소보다 크다면 자리를 그대로 유지한다.

• 그리고 loop을 한 번 돌 때마다 max 길이와 i(=end) - start + 1(=subString의 길이와 같다.)을 비교해준다.

• 다음 사진은 마지막 loop이 끝나고 map과 length의 상태다.
  

수정, 지적을 환영합니다!

문제 링크

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

LeetCode GitHub

https://github.com/tTab1204/LeetCode