leetcode0003 - Longest Substring Without Repeating Characters / Medium / TypeScript

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

Longest Substring Without Repeating Characters - LeetCode

 

Sliding Window 기법 사용

• Set을 사용, startIndex & endIndex 모두 0으로 시작
• endIndex를 1씩 더하면서 Set에 해당 문자를 저장하는데, 이때 중복되는 문자가 등장하면 startIndex를 1씩 더함

Time Complexity, Space Complexity O(N)

• 문자열을 하나씩 훑기 때문에 시간 복잡도, 공간 복잡도 모두 O(n)
• O(n)

function lengthOfLongestSubstring(s: string): number {
    let startIndex = 0;
    let endIndex = 0;

    let characters = new Set();
    let longestLength = 0;

    while(endIndex < s.length) {
        if(characters.has(s[endIndex])) {
            characters.delete(s[startIndex]);
            startIndex++; 
        } else {
            characters.add(s[endIndex]);
            endIndex++;
            longestLength = Math.max(longestLength, characters.size);
        }
    }
    return longestLength;
};