[슬라이딩윈도우][JavaScript][LeetCode] #3. Longest Substring Without Repeating Characters

#슬라이딩 윈도우  #MEDIUM

Longest Substring Without Repeating Characters - LeetCode

🌷 문제 설명

✏️ LeetCode 연습문제: Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.

🎃 제한 사항
0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces.

입출력 예

s	result
"abcabcbb"	3
"bbbbb"	1
"pwwkew"	3

 

🌷 내 코드

1. 셋을 사용한 풀이: Set

var lengthOfLongestSubstring = function (s) {
  let set = new Set();
  let left = 0;
  let maxSize = 0;

  // s의 길이가 0이면 0을, 1이면 1을 반환한다
  if (s.length === 0) {
    return 0;
  } else if (s.length === 1) {
    return 1;
  }

  for (let i = 0; i < s.length; i++) {
    while (set.has(s[i])) {
      //2. set에 다음 알파벳이 있다면, 즉 중복된다면
      set.delete(s[left]); //젤 왼쪽에 있는 값을 지워주고
      left++; // left 인덱스를 올려줍니다
    }
    set.add(s[i]); //1. set에 알파벳 하나씩을 순서대로 넣기
    maxSize = Math.max(maxSize, i - left + 1); //최댓값구하기: i, left 둘 다 인덱스라 1을 더해줌
  }
  return maxSize;
};

2. 배열을 사용한 풀이: Array

var lengthOfLongestSubstring = function(s) {
    let arr = new Array()
    let left = 0
    let maxSize = 0

    if (s.length === 0) {
        return 0
    } else if (s.length === 1) {
        return 1
    } 


    for (let i=0; i < s.length; i++) {
        while (arr.includes(s[i])) {
            arr.shift()
            left++
        }
        arr.push(s[i])
        maxSize = Math.max(maxSize, i-left+1)
    }
    return maxSize
};

 

🌷 코멘트

set과 array 똑같이 가능인데 Set 했을 때랑 Array 했을 때랑 속도 차이가 좀 남!
대신 Array로 했을 때 메모리를 덜 쓰는 경향이 있는 듯?

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview