2019-05-15_16-lengthOfLongestSubstring

string

array

map

first trial:

var lengthOfLongestSubstring = function(s) {
    // console.log(s.split(''))
    let sArr = s.split('');
    let map = {};
    let tempRes = 0;
    let res = 0;

    let tempCount = 0;

    for (let i = 0; i < sArr.length; i++) {
        const char = sArr[i];

        // if map contain the char
        if(map[char] !== undefined){
            tempCount = deletePropBeforIndex(map, map[char], tempCount);
            map[char] = i;
            tempCount++;
        }else{
            map[char] = i;
            tempCount++;
            tempRes = tempCount;

            // test example: 'nfpdmpi'
            // tempRes if updated when map length changed
            // res is stored the bigest value   
            if(tempRes > res) res = tempRes;
        }
        
    }

    return res;
}

deletePropBeforIndex = (obj,index, tempCount)=>{
    for (const key in obj) {
        if (obj.hasOwnProperty(key)) {
            let value = obj[key];
            if(value <= index){
                delete obj[key]
                tempCount--
            }
        }
    }

    return tempCount;
}

console.log(lengthOfLongestSubstring("nfpdmpi"));

// Runtime: 340 ms, faster than 21.84% of JavaScript online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 42.5 MB, less than 19.99% of JavaScript online submissions for Longest Substring Without Repeating Characters.
// From 10:30 - 12: 21

second trial 05-16 09:00 - 10:00 on bus 21:00 - 21:15 at home

// Given a string, find the length of the longest substring 
// without repeating characters.
var lengthOfLongestSubstring = function (s) {
    var sArr = s.split('');
    // at most, res = aArr.length
    var arr = [];
    var res = 0;
    var tempLength = 0;
    for (var i = 0; i < sArr.length; i++) {
        var value = sArr[i];
        var dIndex = arr.indexOf(value);
        // arr contains the value
        if (dIndex >= 0) {
            // delete the subArr from 0 to dIndex
            arr = arr.slice(dIndex + 1, arr.length);
            arr.push(value);
            tempLength = arr.length;
        }
        else {
            arr.push(value);
            tempLength = arr.length;
            res = Math.max(tempLength, res);
        }
    }
    return res;
};

// console.log(lengthOfLongestSubstring("aab"));


// Runtime: 96 ms, faster than 84.26% of JavaScript online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 42 MB, less than 27.72% of JavaScript online submissions for Longest Substring Without Repeating Characters.

refactored

// Given a string, find the length of the longest substring 
// without repeating characters.
var lengthOfLongestSubstring = function (s) {
    var sArr = s.split('');
    var arr = [];
    var res = 0;
    var tempLength = 0;
    
    for (var i = 0; i < sArr.length; i++) {
        var value = sArr[i];
        // the duplication value index
        var dIndex = arr.indexOf(value);
        // if the arr contains the value
        if (dIndex >= 0) {
            // delete the subArr from 0 to dIndex
            // slice function has no side effect
            arr = arr.slice(dIndex + 1, arr.length);
            // remember to push the new value to arr
            // failed in here in thinking, got it through step debug
        }
        
        // all need to push the new value
        arr.push(value);
        tempLength = arr.length;
        
        // update the biggest to res
        res = Math.max(tempLength, res);
    }
    return res;
};

// console.log(lengthOfLongestSubstring("aab"));


Runtime: 76 ms, faster than 99.64% of JavaScript online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 41.6 MB, less than 39.30% of JavaScript online submissions for Longest Substring Without Repeating Characters.

conclusion

use a store(arr vs map) to store scanned value O(1) - O(1)

if a new value existed in the store n* O(n) - n*O(1)

cut the store O(1) - O(n)

save the new value O(1) - O(1)

get the length/size of the store O(1) - O(n?)//Object.keys(obj) complexity

Other submittion

var lengthOfLongestSubstring = function(s) {
    if (s.length <= 1) return s.length;
    
    s = s.split('');
    let seen = {};
    let sub = '';
    let largestSub = '';
    
    for (let i = 0; i < s.length; i++) {
        seen[s[i]] = seen[s[i]] + 1 || 1;
        
        if (seen[s[i]] > 1) {
            sub = sub.substring(sub.indexOf(s[i]) + 1);
        }
        sub += s[i];
        
        if (sub.length > largestSub.length) {
            largestSub = sub;
        }
        
    }
    
    return largestSub.length;
};

/**
 * could also split at every letter and check the lengths of each...
 */
function lengthOfLongestSubstring(x) {
  // console.group(`${x}`)
  const list = x.split('')
  /**
   * @type {string[]}
   */
  let current = []
  let longest = 0

  for (let index = 0; index < list.length; index++) {
    const value = list[index]
    // console.info(current.join(',') || '[]', ';', index, value)

    if (current.includes(value)) {
      // console.log('resetting')

      // if it's the last one...
      const lastIndexOfValue = current.indexOf(value)
      const length = current.length
      const isLast = lastIndexOfValue === length - 1

      // update
      const everythingAfter = current.slice(lastIndexOfValue + 1, length)
      const merged = [...everythingAfter, value]

      // console.log(`
      // length: ${length},
      // lastIndexOfValue: ${lastIndexOfValue + 1},
      // current: ${current.join(',') || '[]'},
      // everythingAfter: ${everythingAfter.join(',') || '[]'},
      // merged: ${merged.join(',') || '[]'},
      // isLast: ${isLast},
      //       `)

      current = isLast === true ? [value] : merged
    } else {
      // console.log('adding')
      current.push(value)
    }

    if (current.length > longest) {
      longest = current.length
    }

    // console.log('
')
  }

  // console.log(current)
  // console.log(longest)
  // console.groupEnd()

  return longest
}

// function test() {
//   console.assert(lengthOfLongestSubstring('pwwkew') === 3, 'pwwkew')
//   console.assert(lengthOfLongestSubstring('bbbbb') === 1, 'bbbbb')
//   console.assert(lengthOfLongestSubstring('abc') === 3, 'abc')
//   console.assert(lengthOfLongestSubstring('aab') === 2, 'aab')
//   console.assert(lengthOfLongestSubstring('dvdf') === 3, 'dvdf')
//   console.assert(lengthOfLongestSubstring('aabaab!bb') === 3, 'aabaab!bb')

/**
 * @param {string} s
 * @return {number}
 */

var lengthOfLongestSubstring = function (s) {
 let res = s.split('').reduce(
        (pre, cur) => {
        let st = pre[0].indexOf(cur);
            if (st > -1) {
                return [
                    pre[0].slice(st + 1) + cur,
                    Math.max(pre[0].length, pre[1])
                ];
            } else {
                return [
                    pre[0] + cur,
                    pre[1]
                ];
            }

        }, ['', 0]
    );
    return Math.max(res[0].length, res[1]);
};