[LeetCode] 3. Longest Substring Without Repeating Characters, Medium

1. 문제

• 문자열 s가 주어질 때, 중복되지 않는 가장 긴 서브 문자열의 길이를 구하라.

2. 해결

function lengthOfLongestSubstring(s: string): number {
    const map = new Map<string, number>();

    // left ~ right 구간을 슬라이딩 윈도우.
    let left = 0;
    let maxLen = 0;

    for(let right = 0; right<s.length; right++) {
        
        const char = s[right];

        // 슬라이딩 윈도우 내 중복된 문자면, 제외 시키고 윈도우 조정.
        if(map.has(char) && map.get(char) >= left) {
            left = map.get(char) + 1;
        }

        map.set(char, right);

        // 윈도우 전 구간 탐색. 6~7까지 후 최고 값 갱신.
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
};

• 슬라이딩 윈도우 미쳐버리겠다.
• 해결하지 못해서 참고했다.
• 슬라이딩 윈도우 내부를 중복되지 않는 문자열만으로 구성되게 하고, 끝까지 탐색하여 가장 길었던 길이를 반환한다.