Algorithm : length of the shortest string

Heechul Yoon·2021년 7월 25일
0

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
};
  1. hash set is used as a unique checker
  2. pointer is used to avoid nested loop
profile
Quit talking, Begin doing

0개의 댓글