[Algorithm] LeetCode - 3. Longest Substring Without Repeating Characters (Hash Table, String, Sliding Window)

 

LeetCode 문제입니다.

[문제설명]

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

 

번역)

Given a string s, find the length of the longest substring without repeating characters.
주어는 문자열 s에서, 반복되지 않은 문자가 없는 가장 긴 문자열의 길이를 구하시오

 

Topic: Hash Table, String, Sliding Window

Level: Medium

Accepted 3,608,442 / Submissions 10,756,223

---

[제한사항]

 

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

---

[입출력]

예시 1

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

예시 2

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

예시 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.

---

[문제풀이]

/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = (s) => {
    
    // helpers
    const checkSubstring = (subStr) => subStr === [...new Set(subStr.split(""))].join("")
    
    if (s === "") return 0
    let result = 1
    
    while (true) {
        let tmp = result
        for (let i = 0; i < s.length - result; i++) {
            let subString = s.substr(i, result + 1)
            if (checkSubstring(subString)) {
                result++;
                break;
            } else {
                continue;
            }
        }
        if (tmp === result) break
    }
    return result
};

첫번째 Code : 

시간 복잡도가...꽝이다.

시간 내에 풀기 위해서 이런 혼종의 코드가 나왔는데 아래의 코드로 sliding winodw와 Hash table 방식이 맞는 것 같음.

 

Idea: 

1. result(length)를 초기화하여 시작해서 답이 나올때까지 구하는 로직

2. checkSubstring helper에서 subStr이 반복되는 문자가 있는지 확인

3. subString이 로직을 만족하는 경우 result 값을 올리고 result+1인 경우도 가능한지 찾기 위해 break

const lengthOfLongestSubstring = s => {
    // keeps track of the most recent index of each letter.
    const map = {};
    // keeps track of the starting index of the current substring.
    var left = 0;
    
    return s.split('').reduce((max, v, i) => {
        // starting index of substring is 1 + (the last index of this letter) to ensure this letter is not counted twice.
        left = map[v] >= left ? map[v] + 1 : left;
        // updates last recorded index of letter to the most recent index.
        map[v] = i;
        
        // indices of current substring is (idx - leftIdx, idx).
        // +1 because if your substring starts and ends at index 0, it still has a length of 1.
        return Math.max(max, i - left + 1);
    }, 0)
};

첫번째 Code : 

Map과 start pointer을 사용해서 시간 복잡도를 O(n)으로 내릴 수 있음

 

---

 

[Performance]

최근 performance가 두번째 코드