(leetcode) Longest Substring Without Repeating Characters

문제 설명

 

문자열 s가 주어졌을 때 반복되지 않는 가장 긴 문자열의 길이를 리턴하는 문제.

 

 

입출력 예

 

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

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

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.

Input: s = ""
Output: 0

 

 

소스

 

슬라이딩 윈도우를 사용한 풀이.

브루트포스로 풀면 O(n3) 이기 때문에 시간초과가 발생할 수 있다.

 

const lengthOfLongestSubstring = function(s) {
    let chars = Array(128).fill(0);
    let left = 0;
    let right = 0;
    let result = 0;
    
    while (right < s.length) {
        let r = s.charCodeAt(right);
        chars[r] += 1;
        
        while (chars[r] > 1) {
            let l = s.charCodeAt(left);
            chars[l] -= 1;
            left += 1;
        }
        
        result = Math.max(result, right - left + 1);
        
        right += 1;
    }
    
    return result;
};

 

다른 풀이

 

const lengthOfLongestSubstring = function(s) {
    const n = s.length;
    let maxStr = '';
    let tempStr = '';
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        tempStr = s[i];
        
        let idx = maxStr.indexOf(tempStr);
        
        if (idx > -1) maxStr = maxStr.slice(idx + 1);
        
        maxStr += tempStr;
        result = Math.max(result, maxStr.length);
    }
    
    return result;
};