3. Longest Substring Without Repeating Characters

문제

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150

 

풀이

해당 문제는 아래의 사진을 참고하며 설명해보자.

 

Set 객체에 값을 넣어주며 중복 처리를 진행한다. 만약 중복된 문자열이 나온다면 왼쪽 포인터를 옮기며 탐색을 진행한다.

 

 

코드

/**
 * @param {string} s
 * @return {number}
 */
// 첫 번째 풀이
// var lengthOfLongestSubstring = function(s) {
//     if(s.length === 0) return 0;
//     let answer = 0;
//     // const newS = s.replaceAll(' ', '0');

//     for(let i = 0; i < s.length; i++){
//         const set = new Set();
//         let cnt = 0;
//         for(let j = 0; j < s.length; j++){
//             const c = s[i + j];
//             if(!c || set.has(c)){
//                 break;
//             }
//             set.add(c);
//             cnt++;
//         }
//         answer = Math.max(cnt, answer);
//     }
//     return answer;
// };

// 두 번째 풀이
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0) return 0;
    const set = new Set();
    let max = 0;
    let lp = 0;

    for(let i = 0; i < s.length; i++){
        while(set.has(s[i])){
            set.delete(s[lp]);
            lp++
        }
        set.add(s[i]);
        if(max < set.size) max = set.size;
    }
    return max;
};