[31일차] Sliding Window 3

문제

Sliding Window - findLongestSubstring

Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters.

findLongestSubstring('') // 0
findLongestSubstring('rithmschool') // 7
findLongestSubstring('thisisawesome') // 6
findLongestSubstring('thecatinthehat') // 7
findLongestSubstring('bbbbbb') // 1
findLongestSubstring('longestsubstring') // 8
findLongestSubstring('thisishowwedoit') // 6

Time Complexity

O(n)

해결책

function findLongestSubstring(str){
  //유효성 체크
  if(str === '' || str === null) return 0; 
  let maxLen = 0; 
  var left = 0;
  var lookup = {};
  
  for(let i = 0; i < str.length; i++){
      if(lookup[str[i]]){
        //이미 존재하는 인덱스 중 큰 것을 다시 세팅
        left = Math.max(left, lookup[str[i]]);
      }

      maxLen = Math.max(maxLen, i - left + 1);
      //인덱스를 세팅 길이 계산을 해야하니 +1 
      lookup[str[i]] = i+1;
  }
  
  return maxLen;
}

출처

https://www.udemy.com/share/105zfq3@SWkkjhuDppThaj9Pv5gWwpcZ60jgT-SQ01nn6lhNMyFJpLfhwJ1r_aVmu4r5HHWpHQ==/