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

Please like the video, this really motivates us to make more such videos and helps us to grow. thecodingworld is a community which is formed to help fellow student and professionals looking to crack the “coding interviews”.

We love solving and sharing problems which are frequently asked in technical interviews and voted by community at various websites.

✅ For more and upcoming updates join our community

#leetcode #python

[ogsconnect]

Welldone! You can further simplify your idea as follows:
1. let i = 0, indicating the start of a substring
2. iterate through the input strings on until you reach a repeated character
3. At that point, move i to a new start which will be the character after the index of the repeated character
4. keep updating max_length as you encounter character by comparing with difference between current index in s and i.

Note: 'i' can never decrease, so take max of current i and new update

see code idea below -

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
i = 0

max_length = 0

seen = dict()

for j in range(len(s)):
if s[j] in seen.keys():
i = max(i, seen[s[j]] + 1)
seen[s[j]] = j
else:
seen[s[j]] = j

if j - i + 1 > max_length:
max_length = j - i + 1

return max_length

[vishalgantyala]

Im losing my intrest on coding after watching these videos

[raahulll]

very helpful, thank you, been stuck on this question for 2 days!

[pritomdasradheshyam]

this is a great and to the point explanation...need more amazon leetcode problem solutions

[YoursTrulyAkr]

s=input("Enter string ")
w=""
for i in range(len(s), 0, -1):
for j in range(0, len(s)-i+1):
s2=s[j:j+i]
if len(set(s2))==len(s2):
w=s2
break
if w!="":
break
print("string is : ", w, " of length : ", len(w))

[harityadav]

we can use enumerate function, it reduce around 4 ms.
map = {}
start = max_length = 0
for i, c in enumerate(s):
if c in map and start <= map[c]:
start = map[c]+1
else:
max_length = max(max_length, i-start+1)
map[c] = i
return max_length

[SatyakiSanyals]

You can do it in O(n) time & constant aux space by storing & referencing previous indexes, & not complicate with dictionaries
pseudo code:
int[] prev = new int[256] // fill prev with -1
// i=starting index of window, j=ending index
int res=0, i=0;
for (int j=0; j<str.length(); j++) {
i = Max(i, prev[str.charAt(i)]+1);
res = Max(res, j-i+1);
prev[s.charAt(i)] = j;
}
return res;

[manoj]

I think the below version is simple. Is it still correct?

keep build substring by looping through the string until new char is not preset in the substring. If presents check if the length of the current substring and verify if that is the longest. Do this length check one more time at the end.

code below...

def longestSubstring(string):
longest = 0
sub = ''
for s in string:
if s in sub:
if len(sub)>longest:
longest = len(sub)
sub = ''
else:
sub += s

if len(sub)>longest:
longest = len(sub)

return longest

[sanyajain]

why have we added start<= map[s[i]] in if condition?

[HRSHU]

Check Out This one:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
temp = ans = ""
for i in s:
if i in temp:
temp = temp[temp.index(i) + 1:]
temp += i
ans = temp if len(temp) > len(ans) else ans
return len(ans)

[meghu]

Thanks so much for the video!
at 8:40 second, I think you forgot to mention dictionary is still updating new values for the repeated characters (a, b, c).

[crypto_everyday_]

The explanation was very clear. Thank you .

[dheerajgupta]

I believe there is something missing for case: pwwkew. Above code will return max(2, 6-6+1) whereas answer is 3.

[abdifatahmoh]

What is the name of app that you drawing you code using your hand writing?

[victorsamsonov]

at 2:33 what did you say? Sliding window technique?

[aleks]

@thecodingworld why does the "start" value have to be less than or equal to the index value in dictionary? i.e., start<=map[s[I]]
I don't understand it at all and couldn't follow anything after this point

[garygoh]

def lengthOfLongestSubstring(s):
# Set to store characters seen so far
seen = set()
# Maximum length substring without repeating characters
max_len = 0
# Start of current substring
start = 0

for i, c in enumerate(s):
if c in seen:
# Remove characters from the start of the current substring until the character is removed
while c in seen:
seen.remove(s[start])
start += 1
# Add the current character to the set
seen.add(c)
# Update the maximum length if necessary
max_len = max(max_len, i - start + 1)

return max_len

[priyankataneja]

What will be the time complexity and space complexity of this??

[kishorem]

Why i hate coding its very tough to me😣😣😣😣😭

[arpittiwari]

I'm getting wrong answer for input ababab