[string] 3. Longest Substring Without Repeating Characters

문제

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

문자열 s가 주어지면, 반복되는 문자 없이 가장 긴 부분 문자열의 길이를 구한다.

예시

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

제약

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

코드

const lengthOfLongestSubstring = (s) => {
    let maxLength = 0;
    let subStr = [];
    
    // for (let i = 0; i < s.length; i++) {
    //     if (subStr.includes(s[i])) {
    //         const idx = subStr.indexOf(s[i])
    //         subStr = subStr.slice(idx + 1);
    //         subStr.push(s[i]); 
    //     } else {
    //         subStr.push(s[i]);
    //     }
    //     maxLength = Math.max(maxLength, subStr.length);
    // }
  
  	[...s].forEach((c) => {
        if (subStr.includes(c)) {
            const idx = subStr.indexOf(c)
            subStr = subStr.slice(idx + 1);
            subStr.push(c); 
        } else {
            subStr.push(c);
        }
        maxLength = Math.max(maxLength, subStr.length);
    }) 
    
    return maxLength;
};

풀이

• 중복되는 문자가 없는 가장 긴 부분문자열을 담기위한 subStr 변수와 가장 길 때의 subStr 의 길이를 담을 maxLength 변수를 준비한다.
• 입력받은 s를 한글자씩 순회하면서 subStr 에 채워 넣는다.
• 그런데 만약 subStr 에 이미 순회하고 있는 문자 c 가 존재하면 subStr 의 첫 글자부터 c까지 전부 삭제하고 c 뒷 부분만 살려둔다. ( subStr = subStr.slice(idx + 1);)
• 매 순회마다. subStr 의 현재 길이와 이전의 maxLegnth 를 비교하여 더 높은 값으로 설정한다.