[LeetCode] Longest Substring Without Repeating Characters - Javascript

Longest Substring Without Repeating Characters

[ 문자를 반복하지 않는 가장 긴 문자열의 길이 구하기 ]

 

제약 조건 

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

 

Example

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.

 

문제 접근 방식

obj 빈 객체를 생성해 s[end] 값이 존재하지 않는다면 obj 객체에 s[end] 값을 key로 넣고 값은 1로 지정하고 end를 증가한다.
[a, b, c, a, b, c, b, b]
위의 배열이 있다고 가정할 때, end가 2가 될 때까지 obj 객체에는 {_a:1, _b:1, _c:1} 값이 들어가 있다.
max는 obj 객체 크기가 되며 3이 된다.
end가 3이 되어 'a'값이 obj 객체에 이미 존재할 경우 else 문으로 들어가 맨 처음 들어간 객체의 키 "_a:1"를 삭제하고 start를 증가시킨다.

전체코드

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
   let obj = {};
   let start = 0;
   let end = 0;
   let max = 0;

   while (end < s.length) {
      if (!obj.hasOwnProperty('_' + s[end])) {
         obj['_' + s[end]] = 1;
         end++;
      } else {
         delete obj['_' + s[start]];
         start++;
      }
      max = Math.max(max, Object.keys(obj).length);
   }

   return max;
};

 

다른 sovle 코드

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let maxLength = 0,
    left = 0,
    chars = new Set();

    for (let i = 0; i < s.length; i++) {
        while (chars.has(s[i])) {
          chars.delete(s[left]);
          left++;
        }

        chars.add(s[i]);
        maxLength = Math.max(maxLength, chars.size);
    }

    return maxLength;
};

위의 풀이도 슬라이싱 윈도우로 풀이했다.

문자열을 반복문으로 돌리며 문자를 해시에 넣고 원소의 개수를 maxLength로 업데이트한다.

만약 이미 존재하는 문자이면 그 문자가 다시 나올 때까지 원소를 제거하며 maxlength를 업데이트했다.