DAY2-Longest Substring Without Repeating Characters[Level: Medium]

문제.Longest Substring Without Repeating Characters

문자열내 중복없이 가장긴 부분 문자열의 length를 구하는 문제이다

여기서 힌트는 “중복없이“인 것 같다. 모든 부분을 반복해서 비교해도 되지만 너무 복잡해지니까 map이나 set을 사용해서 바깥으로 반복한번을 가지고 계산하는게 가장 적합하다는 판단이다

Map or Set.

• map : value를 저장 → set, get, has, delete를 제공\

• set: key:value를 저장 → add, has, delete를 제공

map과 set은 비슷하지만 set은 값의 존재여부만을 관리하고 map은 key:value의 형태로 가지고있기 때문에 지금 같이 글자와 글자위치를 기억해야하는 경우에는 map이 적절하다

풀이 Code.

var lengthOfLongestSubstring = function(s) {
    let map = new Map()
    let left = 0
    let result = 0

    for(let right = 0; right < s.length; right++){

        const currentItem = s[right]
        if(map.has(currentItem)){
            left = Math.max(left, map.get(currentItem) + 1)
        }

        map.set(currentItem, right)
        result = Math.max(result, right - left +1)
    }

return result

슬라이드윈도우를 이용한다 왼쪽부터 창을 인덱스 하나씩 늘려나가며 창내에 중복이 발생하면 왼쪽에서 하나를 버려 창을 줄인다 그렇게 총인데

1. 맵을 생성

2. 창의 왼쪽부분을 담당할 변수 초기화

3. 리턴할 값 즉, 문자열의 최대 길이를 저장하는 변수 초기화

4. 인자로 받을 문자열의 length 만큼 도는 반복문 생성

5. 반복문의 현재 index의 값이 map에 있으면 left를 중복되는 위치까지 끌어올림

6. 그리고 현재 요소를 key로 index를 value로 map에 저장 반복시 비교를 위함임

7. 현재 윈도우 길이와 기존 result 중 큰 값을 비교하여 업데이트