[4월 6일] Longest Substring Without Repeating Characters

1. 문제 : Longest Substring Without Repeating Characters

문제 설명

Given a string s, find the length of the longest substring without repeating characters.

제한 사항

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

풀이

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // 누적합
    const st = [];
    const arr = [];
    let now = 0;
    if(s.length===0) return 0
    s.split('').forEach(it=>{
        if(st.includes(it)){
            if(st.lastIndexOf(it)>=now){
                now = st.lastIndexOf(it)+1;
            }
            st.push(it);
        }else{
            st.push(it);
        }
        arr.push(st.length-now);
    })
    return Math.max(...arr)
};

• s를 순환을 하며 st에 하나씩 집어 넣었다.
• 그리고 now라는 변수를 만들어, 문자가 곂치지 않는 마지노선을 정의하였다. => arr.push(st.length-now)로 값을 arr에 추가하였다.

 

다른 사람 풀이

var lengthOfLongestSubstring = function(s) {
    let max_len = 0;
    let curr = 0;
    let hash = {}; 
    if(s.length < 2) {
        return s.length;
    }
    for(let i = 0; i < s.length;  i++) {
        if(hash[s[i]] == null) {
            curr += 1;
        } else {
            curr = Math.min(i - hash[s[i]], curr + 1);
        }
        max_len = Math.max(max_len, curr);
        hash[s[i]] = i; //save the index
    }
    return max_len;
};

• hash 함수(객체)를 이용했다.
• key=현재 값, value=현재 값의 index 를 저장함으로써, hash[현재값]===null이냐, 아니냐에 따라 풀어주었다.

이 풀이도 괜찮네.

 

---

2. 느낀 점 / 배운 점

1. indexOf(a) / lastIndexOf(a) : 배열에서 문자를 통해 index를 구할 수 있는 메소드

2. s의 길이가 0인 경우, if가 아닌 else의 경우 모두 생각하며 풀어야 함