LEETCODE 3 (JAVASCRIPT) | LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS | CODING INTERVIEW PREP

Longest Substring Without Repeating Characters solution: Leetcode 3 (Javascript)

[@utsavk1]

Nice bro, your videos are very and helpful. Just One suggestion, the audio is little low.

[@tathagat9586]

great video as usual, I love your channel

[@chowtuk]

GOOOD, it's using hashmap to store the string, so that we can compare the string appear only once with the string appear more than once, the windowend equal to the s.length -1 , the window start represent the times string that appear more than once. As the while loop only run for the char stored more than once, we can now use end minus the start to get the char that without repeat.

[@zacharyhorton8046]

function lengthOfLongestSubstring(s) { if (!s.length) return '' let max = -Infinity let set = new Set() // how do we shrink the run when we find a duplicate? let a = 0 for (let z = 0; z < s.length; z++) { if (set.has(s[z])) while (set.has(s[z])) set.delete(s[a++]) set.add(s[z]) max = Math.max(max, z - a + 1) } return max } The time complexity of the lengthOfLongestSubstring() function is O(n), where n is the length of the string s. This is because the function iterates over the string at most once, and each iteration performs a constant number of operations. The space complexity of the function is also O(n), because the function uses a set to store the unique characters in the current substring. In the worst case, all of the characters in the string will be unique, and the set will contain n elements. How does the function shrink the run when it finds a duplicate? The function shrinks the run by moving the left pointer (a) forward until it reaches the first character that is not in the set. This ensures that the substring always contains unique characters. For example, consider the string s = "abcabcbb". When the function reaches the character c at index 2, it will add it to the set and update the maximum length of the substring to 3. However, when the function reaches the next c at index 3, it will find that it is already in the set. Therefore, the function will move the left pointer forward to index 1, which is the first character that is not in the set. The function will then continue iterating over the string, starting at index 1. In the end, the function will return the maximum length of the substring, which is 3.

[@Digitalkmusicproduction]

I think line 19 the else statement could be removed, because if the value is more than one the while loop wouldn't run, so it would never see it. Right? or am I missing something? great video btw

[@tkaycodes4640]

Nice video. I think you made one mistake though - Time Complexity is O(n) in worst case , not O(n^2) Thats why we use two pointers so we can iterate through every time a max of once, and check for optimal solution at each iteration

[@geralddd.g]

True i agree

[@jamesdcosta4813]

Shouldn’t the complexity of brute force method be n! ?

[@user-ks8md2kk2l]

I was asked this exactly interview problem for my intern position vacancy, I didnt pass it tho :D

[@alxx736]

What program do you use for drawing?

[@tathagat9586]

i guess its microsoft whiteboard

[@chitransh118]

Time complexity is o(n^2), could it be optimize??

[@tkaycodes4640]

Its actually O(n)

[@asifayyub4308]

you can jump to the next substring onve you found the repeating char, instead of traversing in this case = S , you can get O(n)

[@yahiahamdan2222]

why i did delete soFar(leftChar);

[@varunnekkanti1683]

Did you figure this out? Definitely took me forever but take the case of "tmmzuxt". First iteration { t: 1 } incrementer Second { t: 1, m: 1 } incrementer Third { t: 1, m: 2 } incrementer During the third iteration, when you check for the rightChar (m in this case) being >1 you enter the while loop. In the while loop you look for the leftChar which is still set to t:1. Since it's set to 1 you delete it. I believe we're deleting it because 'tmm' is no longer a valid sub-string so we don't need to keep track of the frequency of 't' anymore { t: 1, m: 2 } going to delete { m: 1 } decrementer { m: 1, z: 1 } incrementer { m: 1, z: 1, u: 1 } incrementer { m: 1, z: 1, u: 1, x: 1 } incrementer { m: 1, z: 1, u: 1, x: 1, t: 1 } incrementer hope this helps! I hate how long it took me to realize lol

[@TheHipHopVlog]

Just wanted to share my solution with the community: const lengthOfLongestSubstring = (s) => { let seen = new Set () let max = 0 let left = 0 let right = 0 while(right < s.length){ if(!seen.has(s[right])){ seen.add(s[right]) max = Math.max(max, right - left + 1) right ++ } else { seen.delete(s[left]) left++ } } return max; }

[@jyzibzaidi6600]

Is this good to start DSA with javascript

[@tathagat9586]

start with twoSum to understand pointers --> matrix traversal and then go to sliding windows(fixed/variable)-->Stack , q , linked list-->sorting algos-->searching algos-->recursion-->backtracking -->dp-->greedy algo-->graph-->trie

[@eshw23]

I cant hear you at all lol