Longest Substring Without Repeating Characters - Leetcode 3 - Python

Показать описание

0:00 - Conceptual
4:40 - Coding Solution

leetcode 3
#Coding #Programming #CodingInterview #leetcode #neetcode

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

NeetCode

Рекомендации по теме

Комментарии

A very important correction. Not in the code, but in the explanation: We use Set NOT because it stores unique characters, but because (in HashSet) the operation 'contains()' runs in O(1). We really don't need a data structure that maintains unique elements because we are doing that part explicitly using the 'contains()' operation. So the code would run fine even with a regular List. But 'contains()' in List is typically O(n). Hence the choice of (Hash)Set

arunsp

Amazing explanation as always. Just a little trick I found, instead of res = max(res, r - l + 1), we can simply do res = max(res, set.size()), because the size of the set at that point in the loop will be the size of the current substring

dilln

Done thanks!
Sliding window vs two pointer, in sliding window we keep expanding and shrinking the window dynamically, by moving left and right pointers (sliding left side in this case to reduce the window size) until we don’t have duplicates in our window. Then we can increase window by moving right pointer.

Algorithm:
Expand window until you encounter a duplicate, then keep shrinking the window until the duplicate is not in the window anymore. Keep track of longest substring.

Pitfall:
- when shrinking the window, you have to remove the character from your Set data structure as well
- when you encounter a duplicate when expanding the window, the duplicate that needs to be removed won’t necessarily be the one on the left end, it can be inside the window so you have to keep popping till you reach it

mostinho

Hey dude! I really appreciate everything you've been doing with these videos teaching how to solve this algorithms. I have a good understanding of data structures in general but I never actually knew about some techniques that people use to solve these problems. I'm studying algos for almost a week now and when I come across with a complicated one and a I struggle to solve I always come here to see your point of view. Just a comment to show my gratitude.

douglasfrb

You're the best. Got selected at Amazon because of your teaching.

AnmolSingh-sbjj

One of the cleanest solutions i have come across, thanks!!

MrMainak

You could just use hashmap to store the last index of the character and just move you start of the sliding window to the character next to the duplicate one. Rather than erasing all the characters from set.

int s) {
unordered_map<char, int>dict;
int mx =0;
int start =0, end=0;
for(;end<s.length();end++)
{

{
start= dict[s[end]]+1;
}
mx = max(mx, end-start+1);
dict[s[end]]=end;
}
return mx;
}

abebts

This solution does not work for test case 'pwwkew'. Any updates on why it doesn't pass.

shwethaks

Appreciate the content! It might be useful at the end to do a quick summary and run through just to cement the idea. Thanks!

chyyeeah

alternatively you can use:
res = max(res, len(found))
I think that maybe a bit cleaner and intuitive for some.

eddockery

I watched this 3 times, still no idea how is it working :(

xaapt

Why does changing the solution from "While s[r] in charSet" to "If s[r] in charSet" change the result for the scenario when string is "pwwkew"?

lelandconn

It's not 100% correct right ? I'm not sure in Python but I think Set is not guarantee order so removing left most character in set might lead incorrect result. For example:
input: "bcabefg" -> expected result: 6 ('cabefg')

At the point where r = 3, the set is now contains ('b', 'c', 'a) but since it's not ordered it might appear like 'cab', thus we gonna remove all the characters currently in the set
and leads wrong result 4 (befg)
Please correct me if something wrong

ciantim

Space complexity should be o(1) as there are limited number of characters in the alphabet,

bereketyisehak

Your explanations are usually thorough, but I feel like you rushed through this one.

adventurer

Can anyone help me to understand that why are we removing the left most character? aren't we supposed to remvoe the duplicate character which just came in while traversing? i.e. s[right]?? @neetcode

Taranggpt

umm don't u think this will be O(N^2) since we have a nested loop here ?

shaikhevogen

Nice idea.. but i didnt quite understand how we get 0(n) with inner while loop...wouldn't it be 0(n2)?

rams

Very clever solution. But can anyone please tell me what the time complexity is? He has a while loop within a for loop so I'm not sure.

danielbartolini

How is it O(n), as we are using a for and a while loop within
?

ankitasharma

Longest Substring Without Repeating Characters - Leetcode 3 - Python

Longest Substring Without Repeating Characters - Leetcode 3 - Python

LeetCode Longest Substring Without Repeating Characters Solution Explained - Java

Longest Substring Without Repeating Characters - Leetcode 3 - Sliding Window (Python)

LeetCode Exercise In Java - Longest Substring Without Repeating Characters - FAST Solution

L3. Longest Substring Without Repeating Characters | 2 Pointers and Sliding Window Playlist

Longest Substring Without Repeating Characters - LeetCode 3 - JavaScript

Sliding Window Algorithm - Longest Substring Without Repeating Characters (LeetCode)

Python Programming Practice: LeetCode #3 -- Longest Substring Without Repeating Characters

LeetCode #3: Longest Substring Without Repeating Characters

Length of longest substring without repeating characters | LeetCode problem number 3

Longest substring without repeating characters | C++ Placement Course | Lecture 26.3

Longest Substring Without Repeating Characters - LeetCode 3 - Java

LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS | LEETCODE 3 | PYTHON SOLUTION

Leetcode - Longest Substring Without Repeating Characters (Python)

Leetcode 3. Longest Substring Without Repeating Characters

Longest substring without repeating characters | leetcode | python | leetcode 3 | Amazon

Leetcode - Longest Substring Without Repeating Characters (Python)

Longest Substring Without Repeating Characters - LeetCode 3 Python

Java Program To Find Longest Substring Without Repeated Character | Ashok IT

Longest Substring Without Repeating Characters | Live Coding with Explanation | Leetcode - 3

Longest Substring With Without Repeating Characters | Variable Size Sliding Window

Longest Substring Without Repeating Characters | Amazon

Longest Substring Without Repeating Characters (Leetcode 3) - Medium (Hindi)

Longest Substring Without Repeating Characters | Leetcode 3 | Sliding window