- 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
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('\n')
}
// 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]);
};
