# GetLengthOfLongestSubstring

面試題

// Given a string s, find the length of the longest substring 
// without repeating characters.
function getLengthOfLongestSubstring(str) {. }

console.assert(getLengthOfLongestSubstring('') === 0);
console.assert(getLengthOfLongestSubstring('bbbbbbbb') === 1);
console.assert(getLengthOfLongestSubstring('abcccccc') === 3);
console.assert(getL

一開始不好寫法 O(n2)

function getLengthOfLongestSubstring(str) {
  if(str.length == 0) return 0
  let longest = 0;
  let lookup = new Map()
  let startIndex = 0

  
  while(startIndex < str.length-1){
    // acbcdaccc
      for(let i = startIndex; i< str.length; i++){

        if(!lookup.has(str[i])) {
          lookup.set(str[i], 1)
        } else {
         
          longest = lookup.size > longest ? lookup.size : longest
          startIndex++
          lookup.clear()
          break
        }
      
      
    }
  }
  
  return longest
}

console.assert(getLengthOfLongestSubstring('') === 0);
console.assert(getLengthOfLongestSubstring('bbbbbbbb') === 1);
console.assert(getLengthOfLongestSubstring('abcccccc') === 3);
console.assert(getLengthOfLongestSubstring('abbbcccc') === 2);
console.assert(getLengthOfLongestSubstring('acbcdaccc') === 4);
console.assert(getLengthOfLongestSubstring('abccdbaaa') === 4);
console.assert(getLengthOfLongestSubstring('abcdefghijklmnopqrstuvwxyz') === 26);

改進後時間複雜度 O(n)

function getLengthOfLongestSubstring(str) {
  if(str.length == 0) return 0
  let longest = 0;
  let lookup = new Map()
  let startIndex = 0

  
  while(startIndex < str.length-1){
    // acbcdaccc
    
      if(!lookup.has(str[startIndex])) {
          lookup.set(str[startIndex], startIndex)
          startIndex++
      } else {
          startIndex = lookup.get(str[startIndex]) + 1
          longest = lookup.size > longest ? lookup.size : longest
          lookup.clear()
      }
     
  }
  
  
  return longest
}