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

Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.o...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/take...

[@kuldeepdixit1006]

whenever I am looking for an explanation to a problem and I search it on youtube and if I don't find a solution by striver I get disappointed...Love from Flipkart!

[@arnabsarkar5245]

Bro you are a sde at flipkart?

[@shwetanshusinha2690]

The new look of the DSA sheet and the whole website is just way too awesome sir.

[@pavitrasingh7833]

I just cant express my gratitude in words towards this man . the way he simplifies every single thing makes everything appear so easy . I am so glad that I found this channel.

[@hashcodez757]

Hello Bhaiya!! From past few weeks i was not able to watch any of your videos. Was going through depression . But the moment i joined the journey again with you is a blessing. You have a different aura ....just looking at you i just simply forget everything and a new spark is ignited within me. Thank alot Bhaiya for your efforts and helping me!!

[@sahil_bagde]

Just hope for the better friend , I am gone through that🙂😀

[@simple_user000]

I solved it on my own! Your teaching is amazing bhaiya!!!

[@harshvishvakarma2071]

Need such type of teachers

[@shivamjaiswal1263]

hi Striver, Your Graph, DP, binary search playlist are amazing. Please create a playlist for String as well.

[@rushidesai2836]

Binary Search was pretty good I agree!

[@59_sujatachandra76]

You are unstoppable... 🙏🙏 You are the best 🙏🙏

[@monikayadav-wb6pu]

East and west striver bhaiya is best ❤❤

[@AshutoshAnand-o5l]

1 fix in the brute force is that you need to fill the arrays with 0 every time youre moving i. so heres the correctedd brute.public int lengthOfLongestSubstring(String s) { int[] arr = new int[256]; int max = 0; int n = s.length(); for (int i = 0; i < n; i++) { // Reset the array for each new starting point Arrays.fill(arr, 0); for (int j = i; j < n; j++) { // If character at j has been seen, break the loop if (arr[s.charAt(j)] == 1) { break; } // Otherwise, add the character to substring int len = j - i + 1; max = Math.max(len, max); // Remember it arr[s.charAt(j)] = 1; } } return max; }

[@SibiRanganathL]

can i use HashMap instead of hash Array since TC for searching in HashMap is also O(1)

[@AshutoshAnand-o5l]

@@SibiRanganathL yes sure!

[@adilkevin6220]

I think you haven't attached this youtube link in your take youforward site.

[@tanvirahammed3783]

Hi Striver, I'm not sure if this comment will reach you or not, but I just want to say one thing: I've been watching your videos for more than a year now and have covered a huge part of the graph and dynamic programming playlists. Whenever I watch your videos, I really fall in love with your teaching style, and of course, your smile, and sometimes your small jokes. I enjoy your videos, and it feels like you're not just my tutor; it feels like you're someone very close to me, teaching me with fun and pleasure. However, in your recent playlists, I totally miss that. It feels like you're not as friendly anymore; you're just a teacher like any other tutor. Whenever I watch videos from this playlist, sometimes I wonder what happened to you. Why are you so quiet now? Why don't you joke around anymore? After all, I love your work; it's just my opinion.

[@parth_3856]

yeh! i noticed it too! hoping he's doing good in life..

[@sumitgupta310]

agree

[@rushidesai2836]

Google's job is stressful buddy. It takes lot of effort jusy to make these videos.

[@divyanshushukla6981]

Loved your explaination. Bhaiya instead of using a HashMap we can also use a Set. It will save some more memory. class Solution { public int lengthOfLongestSubstring(String s) { int i = 0, j = 0, max = 0; Set set = new HashSet(); while (j < s.length()) { if (!set.contains(s.charAt(j))) { set.add(s.charAt(j)); j++; max = Math.max(max, set.size()); } else { set.remove(s.charAt(i)); i++; } } return max; } }

[@crimemastergogo710]

In else part i think you should remove s.charat(j) not i

[@limitless6189]

great bro thanks

[@aesthetic_vibes_404]

It will take n^2 time

[@Arjun-dj2lc]

Thank you for this wonderful code

[@theee_1]

Very,very smart case where left has to be the rightmost. eg checking in abc, if left is already at 4 and prior presence of b is at 2, we need not update left to 3, instead it should be max of prior instance+1,already present left

[@riteshbisht94]

Great bhaiji 🙏

[@sathishyenuganti4859]

I Always love your explanation ❤

[@technologicalvivek7510]

Bhaiya mene isko freq array banakar easy way me kardiya. class Solution { public: int lengthOfLongestSubstring(string s) { vector freq(256, 0); int i = 0, j = 0; int maxi = 0; int n = s.length(); while (j < n) { if (freq[s[j]] == 0) { freq[s[j]]++; maxi = max(maxi, j - i + 1); j++; } else { freq[s[i]]--; i++; } } return maxi; } };

[@NEUTRON-h5t]

bro can you explain me this code especially this part else { freq[s[i]]--; i++;

[@ayaamverma6742]

@@NEUTRON-h5t when you find that there is a duplicate element, i.e. freq[s[j]] != 0, you start moving the i pointer till that duplicate element is removed from your window. By the time you reach 1 index ahead of the duplicate element, you would have removed the duplicate element. Again, do a dry run to better understand the logic.

[@AyushEditz-hs6pf]

i think this is overcomplicating things. The easy code could be: int n = s.length(); int left = 0; int right = 0; int maxLen = 0; map mpp; int len=0; while (right < n) { if (mpp.find( s[right] ) != mpp.end() ) { left++; right=left; mpp.clear(); } else{ len++; mpp[s[right]] = right; maxLen=max(right-left+1,maxLen); right++; } } return maxLen;

[@U2011-n7w]

best explanation

[@mr_weird3680]

Thanks Brother

[@subee128]

Thank you very much

[@zenilkapadia7572]

Superb raj❤

[@RogithRog]

public static void main( String[] args ) { String s ="pwwkew"; String count =""; int max =0; int count1=0; for(int i=0;i

[@Divyanshu-q5n]

vector< int > mpp(256,-1); int l=0; int r=0; int maxlength=0; while(r=l) l = mpp[s[r]] +1; } mpp[s[r]] = r; maxlength = max(maxlength,r-l+1); r++; } return maxlength;

[@aniketkumar2502]

int lengthOfLongestSubstring(string s) { if(s.size()==0)return 0; int i=0; int j=0; int maxi=1; int n=s.size(); unordered_mapmp; while(j=i) { i=mp[s[j]]+1; } maxi=max(maxi,j-i+1); mp[s[j]]=j; j++; } return maxi; } finally accepted. Thankyou Striver😊for your effort. i like and appreciate you from bottom of my heart.❤

[@PrinceKumar-ef1xf]

00:06 Finding longest substring without repeating characters 02:46 Using 2 Pointers for Substring Generation 04:59 Using hashing to find the longest substring without repeating characters 07:36 Optimizing algorithm using two pointers and sliding window approach 10:02 Understanding two pointer and sliding window approach 12:17 Determine longest substring without repeating characters using hashmap and sliding window 14:45 Updating characters in a sliding window to find longest substring without repeats. 17:06 Sliding window technique for finding longest substring without repeating characters. 19:10 Algorithm explanation and time complexity analysis 21:42 Explanation of sliding window algorithm with two pointer

[@vivekanand9492]

nice explaination

[@heershah239]

with this solution we can make time complexity as O(n) and space complexity O(n) Set set=new HashSet(); int left=0; int right=0; int mxLen=0; String result = ""; while(rightmxLen) { mxLen= right- left +1; result=str.substring(left,right+1); } right++; }else { set.remove(str.charAt(left)); left++; } } return result; }

[@raghavmanish24]

understood striver.....thanku

[@Learner_45]

With set class Solution { public: int lengthOfLongestSubstring(string s) { int n=s.size(); if(n==0) return 0; int l=0,r=0; int ans=1; sets1; while(r

[@lavanyaan2158]

Thank you so much bro

[@ok-jg9jb]

Thanks❤

Thank you so much

[@codeman3828]

Thanks. Understood.

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@oyeesharme]

understood bhaiya

[@bhuvangowda4842]

thank you bhaiii

[@shototodoroki4719]

understood

[@suryas8860]

Time complexity-O(n) only ,no while loop, Check my solution int lengthOfLongestSubstring(string s) { unordered_map mpp; int count=0; int max=0; for(int i=0;i1){ count=min(i- mpp[s[i]].second,count); } mpp[s[i]].second=i; if(count>max){max=count;} } return max; }

[@anilrouto4513]

Hi @takeuforward , I am not getting language specific codes in your website also. In ur website it is showing coming soon. Would you please update the same if u have not updated

[@amanbhatt1087]

for those who are struggling use memset to initialise hash array instead of normal initialization ``` int lengthOfLongestSubstring(string s) { int n = s.length(), maxlen = 0; int l = 0, r = 0; int hash[255]; memset(hash, -1, sizeof(hash)); while (r < n) { if (hash[s[r]] != -1 && hash[s[r]] >= l) { l = hash[s[r]] + 1; } hash[s[r]] = r; maxlen = max(maxlen, r - l + 1); r++; } return maxlen; } ```

[@suhanigupta2861]

What is a memset?

[@suhanigupta2861]

Why does a normal intialization not work on this code?

[@Messi23485]

@@suhanigupta2861 Have you got to know why? If yes please explain

[@suhanigupta2861]

@@Messi23485 No idea as of now

[@--Sreekarsai]

why there is no code submision

[@PranamHegde]

One small addition to the code - the hashmap has to be updated with the location of the right pointer

[@DheerendraSingh-u2m]

Understood❤❤❤

[@DSASolutions]

Helpfull

[@ashishpradhan6250]

Thanku

[@aditya_raj7827]

Understood 😊😊

[@balajik7376]

It will be more helpful if u submit in any coding platform

[@ashj1165]

with the above psuedo code, solved using hashmap: class Solution { public: int lengthOfLongestSubstring(string s) { map mp; int maxLen = 0; int n = s.size(); int l=0, r=0; while(r

[@bijarnia_vikash]

Thank you for your explanation. it was nice.. I solved it.:)

[@ManishKumar-dk8hl]

Bhaiya wala code { BY USING MAP NAAM KI ARRAY } :-- class Solution { public int lengthOfLongestSubstring(String s) { int l=0; int r=0; int[] map=new int[256]; Arrays.fill(map, -1); int maxlen=0; while(r

[@NonameNoname-f2t]

Striverrrrrr❤❤❤❤❤🎉🎉

[@SibiRanganathL]

Understood

[@AyushKumar-bi3qo]

Can we do this longest substring without repeating characters problem using hashmap in Java?

[@shivisingh9975]

Understood!

[@sushma_1704]

Striver❤❤❤

[@aggarwalsachin4854]

class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.length(), l = 0, r = 0, cnt = 0; unordered_set seen; if (n == 0) return 0; while (r < n) { if (r < n && seen.find(s[r]) == seen.end()) { seen.insert(s[r]); cnt = max(cnt, r - l + 1); r++; } else { seen.erase(s[l]); l++; } } return cnt; } };

[@DJ-md3cj]

great

[@mansisethi8127]

why do we need to do that range checking? I didn't understand

[@Praveen2002-e1k]

hy can anyone explain why strivers use hash array instead of the data structure

[@viditmohil7102]

please upload string playlist

[@messiisthebest]

solution in python: class Solution: def lengthOfLongestSubstring(self, s: str) -> int: hashmap={} left=0 right=0 Max=0 while(right

[@VaibhavSharma-f9g]

can we use map here instead of hash array of 255 characters

[@pratyushtripathi1728]

But space complexity increases 😂

[@minalRanjit]

int lengthOfLongestSubstring(string s) { unordered_mapmpp; int ans=0,i=0; int n= s.size(); int cnt = 0; if(s.size()==1){ return 1; } while(i!=n){ if(mpp[s[i]]==1){ ans = max(ans,cnt); cnt=0; mpp.clear(); } mpp[s[i]]++; cnt++; i++; } return ans; } //can anyone explain why it is failing the testcase of "au".

[@VivekSharma-eh2tv]

s= " " . why doesn't it clear this test case

[@Anandsingh-bu5nq]

use vector instead of array

[@vanshgangwar3440]

Can we use map here ?

[@reshmijahaan1880]

where to find the language specific code

[@joychakraborty4367]

❤❤❤

[@The_Shubham_Soni]

Test Case failed on GFG: input = qwertyuioplkjh output=13, correct output=14.

[@bishalmahanta4398]

guys for input string having no repeating characters, i am getting wrong answer(one less than correct length) in leetcode for example input string="aus" ; the correct output is 3; but output from striver's optimal code is 2.Can someone help me out

[@Anandsingh-bu5nq]

its because you used array for hash use vector

[@bishalmahanta4398]

@@Anandsingh-bu5nq thank you its working fine now; changed int hash[256]={-1} to vectorhash(256,-1)

[@rajatrajgautam3224]

@@bishalmahanta4398 what is the difference here between using vector and array? please elaborate

[@shaiksoofi3741]

undersood

[@subhasrisb11tha28]

❤

[@lrchoudhary6875]

int lengthOfLongestSubstring(string s) { int n=s.size(); int ans=0; string a; for(int i=0;i

[@angeldeveloper]

🙌🏻

[@AkashKumarTiwary-u4b]

god

[@sriramsivakumar5567]

Give running code

[@mind_blazed]

Aise Q. Mere se nhi jamte basic jm jate 😢 plz koi batao how can i do ……

[@obamaengineer4806]

solve codeforces qs lots. ur programming and basic thinking will improve loads. solve prev contsets qs

[@mind_blazed]

@@obamaengineer4806 thank you I'll try to solve

[@Cityscapes411]

Same situation mere sath thi kuch months pahle , but now I can solve even medium level questions easily , u just need practice, practice and more practice

[@obamaengineer4806]

@@Cityscapes411 WHICH PLATFORM U SOLVE FROM AND HOW MANY QS PER DAY AND ANY GENERAL TIPS?

[@AdarshSingh-qd6mq]

👍

[@Manikandan__03]

Anybody please give that code for java

[@maneesha5182]

public int lengthOfLongestSubstring(String s) { HashSetmp=new HashSet(); int i=0,j=0,max=0; while(j < s.length()){ if(!mp.contains(s.charAt(j))){ mp.add(s.charAt(j++)); max=Math.max(max,j-i); } else { mp.remove(s.charAt(i++)); } } return max; }

[@SAACHIPANDEY]

10:44

[@rishabsharma5307]

``` int lengthOfLongestSubstring(string s) { unordered_map mp; int i, j, n = s.size(), length = INT_MIN; i = j = 0; while(j < n) { mp[s[j]]++; if(mp[s[j]] == 1) length = max(length, j-i+1); while(mp[s[j]] > 1) { mp[s[i]]--; ++i; length = max(length, j-i+1); } ++j; } return length == INT_MIN ? 0 : length; } ```

[@cenacr007]

us

[@prashantawasthi6825]

pata nhi ye kn log hai jinhe samjh aa raha hai. educated dikhne k lie english bole ja rahe jbki kisi ko bhi english me nahi samjh aata hoga India me

[@devil648]

Please anyone can help me.. Why we use hash[256] ={0};

[@sprihaanand4128]

initially all possible 256 character's frequency is 0

[@DJ-md3cj]

too long video

[@NikhilSingh-ei2ft]

Beginners like me need such explanation. You also would have started from zero only

[@hardikjain-brb]

worst acche se code de doge to kya jayega bakwas explanation

[@supplymeweed]

You are awesome Striver, [Comment down guys, how many leetcode question y'all have solved so far, and in which semester you are currently in ?]

[@SOUVIK-po9jt]

Solved 350+ Qs on Coding Ninjas, started Leetcode this month. I am in 2nd sem of NIT-A CSE

[@obamaengineer4806]

@@SOUVIK-po9jtbkl pagal hai kya

[@Cubeone11]

@@SOUVIK-po9jt tf

[@user-fw4kz3bb4g]

@@Cubeone11 we actually have to compete with these type of guys lol. IITians start cp in 1st sem ive heard, imagine offcampus you sit for the same job interview

[@SOUVIK-po9jt]

@@user-fw4kz3bb4g U r correct. I have many batchmates not only in CSE but also other branches who are well-versed in CP and won CP competitions organised by our college

[@Shivi32590]

understood

[@adityapandey23]

Understood

[@pardhi8959]

Striver❤

[@hemanthkumarng8996]

❤❤❤

[@Isagi__000]

❤❤