3. Longest Substring Without Repeating Characters

LeetCode 3번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Longest Substring Without Repeating Characters - LeetCode

풀이

아이디어

• 슬라이딩 윈도우
• left와 right 두 포인터를 이동시키면서 중복 없는 부분 문자열을 찾는다.
• 중복 문자를 체크하기 위해서 set을 활용함.

중복 제거 시에 left를 한칸만 오른쪽으로 옮겨주고 다음 루프로 돌아가게 했었는데, 다음 루프에서 남아 있던 중복들이 알아서 없어질 줄 알았는데 아니었다.

코드

function lengthOfLongestSubstring(s: string): number {
    // 문자열의 문자가 1개 이하인 경우 해당 문자열이 최대 길이 substring
    if (s.length <= 1) return s.length;

    let maxLength = 1; // 최소 substring 길이는 문자 하나 길이인 1
    const charSet = new Set()
    let left = 0, right = left + 1;

    charSet.add(s[left]);
    while (left < right && right < s.length) {
        // right의 문자가 charSet에 없을 때 까지 까지 left를 이동
        while (charSet.has(s[right]) && left < right) {
            charSet.delete(s[left]);
            left++;
        }
        // substring 길이 업데이트하기
        maxLength = Math.max(maxLength, right - left + 1);
        // right를 오른쪽으로 한칸 옮기기
        charSet.add(s[right]);
        right++;
    }

    return maxLength;
};