[Sliding Window] Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

본 문제는 해결하지 못했습니다.

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

  for(let i = 0; i < s.length; i++) {
    let substr = s[i];    
    
    for(let j = i + 1; j < s.length; j++) {            
      if(s[i] === s[j]) {                      
        break;
      }      

      if(s[j] === s[j + 1]) {
        substr += s[j];  
        break;
      }

      substr += s[j];
    }        
    max = Math.max(max, substr.length);
  }

  return max;
};

Example 1에서 막혔습니다. 필자는 abca와 같이 탐색 기준이 되는 문자 a가 반복될 때 substring으로 인지하기 때문입니다.

Input		: s = "abcabcbb"
Output		: 4  (i = 3, substr ="abcb")  
Expected	: 3

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using sliding window with set

해답의 전문은 링크를 확인해주세요.

/**
 * @param {string} s
 * @return {number}
 
 * Runtime	: 55 ms
 * Memory	: 47.1 MB
 */
var lengthOfLongestSubstring = function (s) {
  let set = new Set();
  let left = 0;
  let maxSize = 0;

  for (let i = 0; i < s.length; i++) {

    while (set.has(s[i])) {
        set.delete(s[left])
        left++;
    }
    set.add(s[i]);
    maxSize = Math.max(maxSize, i - left + 1)
  }
  return maxSize;
}

본 해답은 set 자료구조로 substring으로 인지하기 위한 문자를 기억합니다. 이로써 필자의 해답과 달리 abcb와 같은 문자열에서 bcb가 substring으로 타당하지 않기 때문에 걸러낼 수 있습니다.