[LeetCode] 3. Longest Substring Without Repeating Characters

해쉬맵을 사용하여 해당 알파벳이 등장한적이 있는지를 판별하고, 이미 등장한 알파벳이 나왔다면 시작점을 해당 알파벳의 인덱스로 부여한 후 재개한다

시간복잡도는 O(n) 선형 그래프이다.

function lengthOfLongestSubstring(s: string): number {
    // 문자의 마지막 등장 위치를 저장하는 Map
    const lastSeen = new Map<string, number>();
    let start = 0; // 현재 부분 문자열의 시작 인덱스
    let maxLength = 0; // 가장 긴 부분 문자열의 길이

    // 문자열을 순회하며 각 문자를 확인
    for (let end = 0; end < s.length; end++) {
        const char = s[end];
        
        // 현재 문자가 이미 등장했고, 그 위치가 현재 부분 문자열의 시작 이후라면
        if (lastSeen.has(char) && lastSeen.get(char)! >= start) {
            // 시작 위치를 이전에 등장한 위치 다음으로 이동
            start = lastSeen.get(char)! + 1;
        } else {
            // 현재까지의 부분 문자열 길이와 최대 길이를 비교하여 업데이트
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        // 현재 문자의 위치를 Map에 저장 또는 업데이트
        lastSeen.set(char, end);
    }

    return maxLength;
}