This posting is about the better way to solve the algorithmn problem in Leetcode
there is a set of string as input
input :
abcdabc
and output is the max length of the substring of the input.
each member of the substring is to be unique
output:
4
so output is the length of abcd
here is my first conclusion that I came to
var lengthOfLongestSubstring = function(st) {
const s = st.split('')
if (st.length === 0) {
return 0
}
else if (st.trim().length === 0) {
return 1
}
let subString = ''
let subStrings = []
for (let i=0; i <= s.length-1; i++) {
for (let j=i; j <= s.length-1; j++) {
subString += s[j]
if (j === s.length-1) {
if (subString.includes(s[j])) {
subStrings.push(subString)
subString=''
}
} else if (subString.includes(s[j+1])) {
subStrings.push(subString)
subString=''
}
console.log(subString)
}
subString = ''
}
const result = subStrings.reduce((prev, current) => {
return (prev.length > current.length) ? prev : current
})
return result.length
};
which is just simple linear search for the substring that has unique member with nested loop.
the time complexity would be logn2
let us imagine one of the worst case
input :
alkjqweoifjsadjfoaij oijewoifjwoiefjowiejfoifjo283u984u293fafvnlkdsfjoiajdoijvmlkczmlkvml!@#@#$%R@$T#%Y%^U&%^HGFDSGSDFfa;dksfjaijefoiajsdlfkva#$E!@#$ERF
with my first solution, the time complexity is input.length * input.length
In order to cut down the time complexity, I reached to the conclusion as follow
var lengthOfLongestSubstring = function(s) {
const ss = s.split('')
let p1 = 0
let p2 = 0
let max = 0
const container = new Set()
while (p2 < ss.length) {
if (!container.has(ss[p2])) {
container.add(ss[p2])
max= max < container.size ? container.size : max
p2+=1
} else {
container.delete(ss[p1])
p1+=1
}
}
return max
};