[리트코드] 3. Longest Substring Without Repeating Characters

안녕하세요. 개발조각입니다.😊

처음으로 리트코드에서 Medium문제를 풀어서 기분이 좋네요.

 

그럼 바로 해결방안에 대해 설명하겠습니다.

---

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

Longest Substring Without Repeating Characters - LeetCode

 

해결방안

var lengthOfLongestSubstring = function(s) {
    if(s.length === 0) return 0;

    let arr = [];
    let strLength = 1;
    
    for(let i=0; i<s.length; i++){
        if(i===0){
            arr.push(s[i]);
            continue;
        }
        
        let str = s[i];
        let idx = arr.indexOf(str);
            
        if(idx > -1) arr = arr.slice(idx+1);
        arr.push(s[i]);
        
        if(idx === -1 && strLength < arr.length) strLength = arr.length;
            
    }
    return strLength;
};

 

if(s.length === 0) return 0;

문자열 s가 0일 경우가 있기 때문에 넣어주었습니다.

 

 

아래의 예제를 토대로 어떻게 진행이 되는지 설명하겠습니다.

Input: s = "abcabcbb"

 

 

i=0일 경우

if(i===0){
    arr.push(s[i]);
    continue;
}

arr = ['a']

 

i=1일 경우

str = 'b'

idx = -1 (arr['a']이므로)

arr = ['a', 'b']

strLength =  2 (idx가 -1이고 arr의 길이가 strLength보다 크므로)

 

i=2일 경우

str = 'c'

idx = -1 (arr['a', 'b']이므로)

arr = ['a', 'b', 'c']

strLength =  3 (idx가 -1이고 arr의 길이가 strLength보다 크므로)

 

i=3일 경우

str = 'a'

idx = 0 (arr['a', 'b', 'c']이므로)

arr = ['b','c'] (idx가 -1보다 큼으로 arr에서 idx위치부터 뒤까지 남기기)

arr = ['b', 'c', 'a']

 

i=4일 경우

str = 'b'

idx = 0 (arr['b', 'c', 'a']이므로)

arr = ['c', 'a'] (idx가 -1보다 큼으로 arr에서 idx위치부터 뒤까지 남기기)

arr = ['c', 'a', 'b']

 

i=5일 경우

str = 'c'

idx = 0 (arr['c', 'a', 'b']이므로)

arr = ['a', 'b'] (idx가 -1보다 큼으로 arr에서 idx위치부터 뒤까지 남기기)

arr = ['a', 'b', 'c']

 

i=5일 경우

str = 'b'

idx = 1 (arr['a', 'b', 'c']이므로)

arr = ['c'] (idx가 -1보다 큼으로 arr에서 idx위치부터 뒤까지 남기기)

arr = ['c', 'b']

 

i=5일 경우

str = 'b'

idx = 1 (arr['c', 'b']이므로)

arr = [] (idx가 -1보다 큼으로 arr에서 idx위치부터 뒤까지 남기기)

arr = ['b']

 

strLength =  3

 

let str = s[i];
let idx = arr.indexOf(str);

if(idx > -1) arr = arr.slice(idx+1);
arr.push(s[i]);

결국 이 부분은 문자열 s에서 중복된 알파벳이 있으면 그 위치만큼 빼준 뒤에 더해주고 아닐 경우에는 더해주기만 합니다.

 

if(idx === -1 && strLength < arr.length) strLength = arr.length;

이 부분에서 strLength 즉 문제의 답을 구하는 부분입니다.