[leetcode] 3. Longest Substring Without Repeating Characters

문제링크

https://leetcode.com/problems/longest-substring-without-repeating-characters/

input & output

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.

Example 4

Input: s = ""
Output: 0

---

Approach #1

/*
input: string
ouput: integer
constraints:
    - 
edge case:
    - if(!s) return 0;

ds: set
Algo: sliding window

Input: s = "abcabcbb"
      left        ^
            
      
set= a b c
size 3

*/

Solution #1

//N:s.length 
//time: O(N)
//space: O(N)
var lengthOfLongestSubstring = function(s) {
  let result = 0;
  let set = new Set();
  let left = 0;
  for (let i=0; i<s.length; i++){
      while(set.has(s[i])){
          set.delete(s[left]);
          left++;
      }
      set.add(s[i]);
      if (set.size > result){
          result = set.size;
      }
      //console.log(set)
  }
  return result;
};

Time Complexity

O(N)

N: s의 길이
s의 길이 만큼 for문을 돌며 set에 문자를 넣고, 빼고, result를 계산하기 때문

Space Complexity

O(N)

N: s의 길이
worst case: s의 문자들이 모두 다른문자들일 경우.
set의 최대 크기가 s의 길이만큼 될 수 있기 때문이다

---

Approach #2

/*
"abcabcbb"
  ^
    ^
Output: 3

bca

"qrsvbspk"
    ^
      ^
vbs
*/

Solution #2

var lengthOfLongestSubstring = function(s) {
  // edge case
  if(s.length === 0 || s.length === 1) return s.length;
  
  let left=0, right=0;
  let maxLength=0;
  const set = new Set();
  
  while(right<s.length){
      let curChar = s[right];
      if(set.has(curChar)){
          while(s[left]!==curChar){
              set.delete(s[left]);
              left++;
          }
          set.delete(s[left]);
          left++;
          set.add(curChar);
      } else{
          set.add(curChar);
          maxLength = Math.max(maxLength, set.size);
      }
      right++;
  }
  return maxLength;
};

Time Complexity

O(N)

N: s의 길이
s의 길이 만큼 while문 돌며 set에 문자를 넣고, 빼고, result를 계산하기 때문

Space Complexity

O(N)

N: s의 길이
worst case: s의 문자들이 모두 다른문자들일 경우.
set의 최대 크기가 s의 길이만큼 될 수 있기 때문이다

---

Solution #3

// time: O(N)
// space: O(N)
// b:true 
// max: 3
//"abcabcbb"
//        ^
//         ^
var lengthOfLongestSubstring = function(s) {
    let i=0, j=0;
    let max =0;
    let map = new Map();
    
    while(j<s.length){ 
        if(map.has(s[j])){
            max = max < j-i? j-i : max;
            while(s[i] !== s[j]) {
                map.delete(s[i]);
                i++;
            }
            i++;
            
        }else map.set(s[j],true);
        
        j++;
    }
    if(i < s.length){
        max = max < j-i? j-i : max;
    }
    return max;  
};

Time Complexity

O(N)

N: s의 길이
s의 길이 만큼 while문 돌며 map에 문자를 넣고, 빼고, max를 계산하기 때문

Space Complexity

O(N)

N: s의 길이
worst case: s의 문자들이 모두 다른문자들일 경우.
map의 최대 크기가 s의 길이만큼 될 수 있기 때문이다