[LeetCode] 3. Longest Substring Without Repeating Characters

https://leetcode.com/

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

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.

 

Constraints:

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

 

Code :

var lengthOfLongestSubstring = function(s) {
    let maxLength = 0,     // 가장 긴 부분 문자열의 길이를 저장하는 변수
        left = 0,           // 현재 부분 문자열의 시작 인덱스를 나타내는 포인터
        chars = new Set();  // 현재 부분 문자열에 포함된 문자들을 저장하는 Set
    // 문자열을 순회합니다.
    for (let i = 0; i < s.length; i++) {
        // Set에 현재 문자가 존재할 때까지 왼쪽 포인터를 이동시키면서 중복 제거
        while (chars.has(s[i])) {
            chars.delete(s[left]);
            left++;
        }
        // 현재 문자를 Set에 추가하고, 가장 긴 부분 문자열의 길이 갱신
        chars.add(s[i]);
        maxLength = Math.max(maxLength, chars.size);
    }
    // 최종적으로 얻은 가장 긴 부분 문자열의 길이를 반환
    return maxLength;
};

 

Solutions Code :

var lengthOfLongestSubstring = function(s) {
    let set = new Set();    // 현재 부분 문자열에 포함된 문자들을 저장하는 Set
    let left = 0;           // 현재 부분 문자열의 시작 인덱스를 나타내는 포인터
    let maxSize = 0;        // 가장 긴 부분 문자열의 길이를 저장하는 변수
    // 예외 처리: 빈 문자열일 경우 0을 반환
    if (s.length === 0) return 0;
    // 예외 처리: 문자열의 길이가 1일 경우 1을 반환
    if (s.length === 1) return 1;
    // 문자열을 순회합니다.
    for (let i = 0; i < s.length; i++) {
        // Set에 현재 문자가 존재할 때까지 왼쪽 포인터를 이동시키면서 중복 제거
        while (set.has(s[i])) {
            set.delete(s[left]);
            left++;
        }
        // 현재 문자를 Set에 추가하고, 가장 긴 부분 문자열의 길이 갱신
        set.add(s[i]);
        maxSize = Math.max(maxSize, i - left + 1);
    }
    // 최종적으로 얻은 가장 긴 부분 문자열의 길이를 반환
    return maxSize;
};

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode