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.
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.
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
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
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
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
great video as usual, I love your channel
Nice bro, your videos are very and helpful. Just One suggestion, the audio is little low.
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.
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.
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
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
True i agree
Shouldn’t the complexity of brute force method be n! ?
What program do you use for drawing?
i guess its microsoft whiteboard
I was asked this exactly interview problem for my intern position vacancy, I didnt pass it tho :D
Time complexity is o(n^2), could it be optimize??
Its actually O(n)
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)
Is this good to start DSA with javascript
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
why i did delete soFar(leftChar);
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
I cant hear you at all lol