Longest Substring Without Repeating Characters (슬라이딩 윈도우 패턴으로 해결하기)

TO-DO

중복 문자가 없는 가장 긴 부분(이어진) 문자열의 길이를 리턴해야한다.

• substring 제작에 사용된 문자를 key, 사용한 알파벳의 인덱스를 value 로 하는 객체 seen을 사용한다.
• 두 개의 포인터를 활용한 슬라이드 윈도우 방식으로, start 는 substring 의 시작 지점을 나타내고, i가 하나씩 증가하면서 인자 str을 순회하는 동안 슬라이딩 윈도우에 해당하는 서브 문자열을 늘려나간다.
• 이미 사용한 알파벳인지 아닌지는 seen에서 조회해서 확인한다.
• 이미 사용한 알파벳이라면, 슬라이딩 윈도우의 시작지점(start)은 변경된다.
• substring 을 늘려가면서 슬라이딩 윈도우에 넣고, 새로운 substring 이 만들어질 때 최대 길이(longest)를 update 한다.

const findLongestSubstring = (str) => {
  let longest = 0; // 최종적으로 반환되는 문자열의 길이, 초기값은 0
  let seen = {}; // key: 알파벳, value: 해당 알파벳이 나타난 index
  let start = 0; // 가장 긴 문자열이 시작되는 인덱스(str 기준) 
 
  for (let i = 0; i < str.length; i++) {
    let char = str[i];   
    if (seen[char]) {
       // 이미 한 번 나온 문자일 경우 
      start = Math.max(start, seen[char]);
    }
    /*가장 긴 문자열의 길이는 지금까지 나온 가장 긴 문자열의 길이와, 현재 인덱스에서 substring의 첫번째 글자 index를 뺀 차이 +1을 해서 현재 글자까지 포함한 문자열의 길이를 비교해서 더 큰 값이 된다. */
    
    longest = Math.max(longest, i - start + 1); 
    //  중복으로 더하는 것을 방지하기 위해 알파벳 키의 value 는 index+1 로 저장한다.
    seen[char] = i + 1;
  }
  return longest;
}