Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters | Amazon

Рет қаралды 281,764

Күн бұрын

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- Check out website: In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE) ..
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
✅Entire Series: bit.ly/placementSeries
✅Problem link: leetcode.com/problems/longest...
✅ Kadane's Link: • Maximum Subarray Sum |...
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements

Пікірлер: 235

@takeUforward 3 жыл бұрын

Understooooooooooooooood? . Instagram(connect if you want to know how a SDE's normal life is): instagram.com/striver_79/ . . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily

@MANOJSHARMA-tw8gg 3 жыл бұрын

Aapki life normal toh nahi hai Supernatural powers 🔥😀

@sahukarinaveenkumar3188 3 жыл бұрын

for moving left pointer why you are taking Math. max( lastoccurence+1, left)? Got confused with this 😒

@learnwithme7750 3 жыл бұрын

yes please tell this

@aryangupta867 3 жыл бұрын

I have a genuine doubt. Like while using the below code it worked on GFG int longestUniqueSubsttr(string S){ int left=0; int right=0; int n=S.length(); int maxlen=0; vectormp(256,-1); // unordered_mapindex; while(right

@Sweety-rx8zq 3 жыл бұрын

Why O(2N) ? Can someone plz explain...

@anoopkumar8732 3 жыл бұрын

10:27 Space Complexity should be O(1) because the set can contain at max all the 26 alphabets. It won't increase more with the size of data.

@takeUforward 3 жыл бұрын

O(256) to be precise, thanks for the correction.

@AbhishekKumar-vr7sh 2 жыл бұрын

@@takeUforward and also the time complexity of the brute force soln would be O(n*256) as we break from the inner loop as soon as we encounter duplicacy which in the worst case won't exceed 256.

@aysams2 Жыл бұрын

why would it be O(1). I ddin't understand

@deepakpallavalli3513 Жыл бұрын

@@aysams2constant space irrespective of length of the string

@studyafa7159 11 ай бұрын

Can some one Please summarise what would be the Space complexity ..? O(1) Or O(n)

@devanshmesson2777 3 жыл бұрын

Striver, your explanation is best, our college teachers never took such pain to explain a certain concept. Thank you so much striver!❤️

@Aryan-oc1fq 9 ай бұрын

was confused as to how you were passing in a char as an input for the vector. for anyone wondering when you pass in a char when an int is expected in a vector array, the char is converted automatically to its ascii value which is an int i.e mpp['a'] becomes mpp[97] as a ascii=97. also, the vector is being used as a hashmap with key: value being index:value.

@premnaath-varadharajan 3 жыл бұрын

one correction, the space complexity of this problem is O(1) not O(n) because even if we include all ascii characters, we only have 256 and this 256 does not change with respect to the size of problem, hence O(1) Thanks for the content bro, from down south!

@omprakashhardaha7736 2 жыл бұрын

Nice 🤘 You u got placed

@sunilgrover4178 2 жыл бұрын

@@omprakashhardaha7736 What are you trying to say?

@omprakashhardaha7736 2 жыл бұрын

@@sunilgrover4178 😂😂 I ask him Ki place hua ya nhi Heavy English 😃

@sunilgrover4178 2 жыл бұрын

@@omprakashhardaha7736 Achha 😂

@omprakashhardaha7736 2 жыл бұрын

@@sunilgrover4178 😅

@amanbhadani8840 2 жыл бұрын

It was so much easy explanation by you that i understood the whole concept in just single go and didn't require to see the code.

@sandeepkohli3281 3 жыл бұрын

Bro I truly Love ur Videos . I love the way you explain and u r such a honest person . I started doing Competitive programming because of ur information on how imp is CP to get high position in tech community. I truly loving the CP as I move deep in the problems

@satyamsrivastava9034 3 жыл бұрын

I don't know why your explanation to the problem is so good.. I have done this problem but I really understood it with your explanation thanks

@neerajgarg9096 2 жыл бұрын

*Code for 2nd Approach* int Solution::lengthOfLongestSubstring(string A) { int n = A.length(); int maxi=INT_MIN;; int i=0,j=0; unordered_sets; while(j

@neerajgarg9096 2 жыл бұрын

T.C- O(2N)*

@raghavgupta00 Жыл бұрын

but it gives TLE when you run this code for the question on gfg in worst case its O(N^2) @striver

@ishanshah3309 2 жыл бұрын

This is very good explanation for the problem. Actually this is lc medium problem but the explanation of striver made it look like an easy problem

@soumyadipsaha8904 3 жыл бұрын

u are explaining better day by day, video after video👌👌

@takeUforward 3 жыл бұрын

Thank you so much 😀

@curiocity4642 3 жыл бұрын

This question was asked in lot of my interviews , Thank you :)

@aniketmasram6500 3 жыл бұрын

Can u tell Which interview ?

@curiocity4642 3 жыл бұрын

@@aniketmasram6500 got asked in my zoho interview last week

@kratitamrakar4779 2 жыл бұрын

But it doesn't pass all the test cases.

@pranavpatki 2 жыл бұрын

@@kratitamrakar4779 It passes

@sharathnair2790 3 жыл бұрын

Man. Screw them who criticize you. Yeh tho bawaal hai. I never understood such difficult sum so easily. Now with the approach that you said i can code it very easily. Thank you very much. You should be reaching to the masses of computer science students globally. Greatly appreciable

@varuncu2756 3 жыл бұрын

This solution is sooo well explained. thanks a lot!!!

@shreyanshjain6861 3 жыл бұрын

Probably the best explanation for this problem, dont know why some people have disliked this video !

@takeUforward 3 жыл бұрын

Let them, no issues :)

@aishwarya1895 3 жыл бұрын

Thanks A bunch bruh for this series though I dont need it now but i came here to support your video. Thanks again for ur guidance ✌

@ritankarsarkar9394 3 жыл бұрын

previous videos so good, mostly figured this out on my own 💕

@ahishnar1568 3 жыл бұрын

Superb shifting of l to direct next position and even superb thing is we don't have to remove the intermediate characters from map instead we just have to check whether intermediate char is present in our window or not. This thing was so beautiful. And this is actually called as optimization.

@sans.creates 3 жыл бұрын

you're doing a wonderful work, sir!! thanks!!

@anuragsrivastava3416 3 жыл бұрын

the implementation part is more attractive than the logic itself !!

@ramakrishnabolisetty8550 3 жыл бұрын

I love your videos bro becoz your videos contain naive and optimal along with intuition ,so I love your videos bhaiyya...thanks a loooooooooooooooot.

@abhimanyu6534 3 жыл бұрын

Best explanation ever No one can explain better than u

@parthh3963 2 жыл бұрын

can anyone explain how that vector mpp(256,-1) is working as a map??

@EntEduRealm 2 жыл бұрын

kzfaq.info/get/bejne/rK6KnbCc17nHYoE.html

@ranasauravsingh 2 жыл бұрын

UNDERSTOOD... !!! Thanks striver for the video... :)

@UHemanthaKumar 3 жыл бұрын

I wonder how can a person can get this solution intuition using map ! amazing explanation bro!

@LloydSmithsonian 2 ай бұрын

this is fabulous! you are awesome! thanks for the video!!!

@christianndouyangdoba8024 5 ай бұрын

Very interesting explanation. I am a beginner-level in algorithms. As I am learning, I want to know the theory behind your approach in solving this problem 🙏

@ashishverma1382 2 жыл бұрын

your explanation is wonderful

@sanketh768 9 ай бұрын

thank you sir, this helped me understand it very clearly

@Sillysmiles76 Жыл бұрын

I really love this series. I'll be always thankful to Striver :)

@saivarun6488 5 ай бұрын

if we use set, it will insert in ascending order and if we use unordered it will take randomly

@GauravKumar-dw2ml 2 жыл бұрын

Thanks for clearing the doubt striver.

@being.popular 3 жыл бұрын

Yes bhaiya, Understood. You are doing a really great job, bhaiya. We are really really grateful to you.

@saunaknandi1814 2 жыл бұрын

THe space complexity should be O(26) i.e O(1) because at max map size can be 26 not more than that

@LaveshGarg 3 жыл бұрын

solution is very well explained thanku bhaiya

@BoostedPLAYER1 2 жыл бұрын

def Solve(string): seen = {} longestLength,i,j = 0,0,0 while j < len(string): if string[j] in seen: i = max(i, seen[string[j]]+ 1) longestLength = max(longestLength,j-i +1) seen[string[j]] = j j += 1 return longestLength

@gauravidesigns 3 жыл бұрын

Instead of the set we can also take a dictionary (python) or hash map and emulate the same, In this case, we do not have to move left pointer 1 by 1 but instead, we can check from the dictionary, how much we need to move the left pointer.so, we can directly write this.

@rajavikramaditya2536 3 жыл бұрын

that approach has been explained..

@gauravidesigns 3 жыл бұрын

@@rajavikramaditya2536 I know you have explained it .I just stopped at when you were using set and the I used map instead of set.I then watched your video furthur .thankyou sir for an awesome explanation

@magicmagus1459 2 жыл бұрын

But I think it might not work with hashmap bc take example of “afbcb”....once right pointer gets to position 4...u simply can’t move left pointer to position 3....hashmap still contains letters ‘a’ and ‘f’ which need to be removed from Hashmap...how will u remove that without moving left pointer one by one using a set

@purnamritab Жыл бұрын

In an example like bbbbb won't both left and right pointers move n times each then the worst case is still O(2n), though, for many test cases, this approach is more optimized than the previous one? Correct me if I am wrong.

@rickk3300 Жыл бұрын

Exactly!! in an example like "bbbb", the time complexity of the final approach will go upto O(2N). I had this doubt too.

@Sillysmiles76 Жыл бұрын

Understood. Easy explanation

@bhagyashri863 2 жыл бұрын

Great explanation .... thank you ☺️

@oqant0424 2 жыл бұрын

last approach was just lit🙌

@syedhabeebuddin101 3 жыл бұрын

Thanks a lot STRIVER !

@anubhavsingh8144 3 жыл бұрын

#FEEDBACK If u could display codes in Python in your upcoming videos it would be much help to Python faternity as well.

@takeUforward 3 жыл бұрын

For that I will have to learn Python in deep, I only know basic syntax :|

@nn_yt24 3 жыл бұрын

Love your content bro...keep up the good work 👍👍👍

@whylifts 3 жыл бұрын

Amazing content brother, can you tell which software you use to teach? it would be really helpful.

@takeUforward 3 жыл бұрын

Wacom tablet and nothing else.

@satyamgupta6030 Жыл бұрын

@umeshpatil1759 3 жыл бұрын

yes ,understood ...............................

@dhruvkaran9724 2 жыл бұрын

classic question , soooooper classic explaination

@user-xd1ql4zm5m Жыл бұрын

yep

@umeshkaushik710 5 ай бұрын

Bhaiya can you please complete the Sliding window playlist from A-Z sheet

@geek_for_life 2 жыл бұрын

Awesome Explaination!🔥

@anujraomnnit 6 ай бұрын

Thank You Striver

@tanmaysatsangi131 2 жыл бұрын

Hello bro, Suppose the array contain all duplicates elements(Ex: {b, b, b, b, b}) then at time the time complexity of last approach goes to O(2N) ??

@tanmaysatsangi131 2 жыл бұрын

I have one more question, after saw the comments should I consider space complexity is O(1) or O(N) ??

@aaravgulati2 11 ай бұрын

1. yes 2. O(1)

@neetisaharan1340 3 жыл бұрын

amazing explanation!!

@mohdtalha4467 3 жыл бұрын

Good Explanation #programmingsolutions

@prashantsingh5907 2 жыл бұрын

Nicely explained striver!!!!

@systemforge 3 жыл бұрын

Woah.. third approach 🔥🔥🔥

@preplikepro3361 2 жыл бұрын

Although he told the whole soln using map but in the code vector is used instead of map.Can anyone give some clarity on that?

@piyushsarraf9994 3 жыл бұрын

In the map approch why not clear map if we see a repeated value, cause whole substring before the repeating character Is waste.

@indrajitdas9553 Жыл бұрын

"if (mpp[s[right]] != -1)" you don't need to check this condition as by default is -1 and you only update left if it has greater value than that and min of left is 0

@jaswantrohila3776 3 жыл бұрын

TOO GOOD EXPLAINATION BRO

@vaishnavi9755 2 жыл бұрын

Can anyone help me understand why O(2*N) complexity for the second solution even when for every outer loop there is an inner loop which will get used when a repeated element appears.

@tahaansari5621 2 жыл бұрын

There's only one loop and O(2N) is the worst time complexity when u would have to move your left index till the end of the array, one by one. So, u would visit each elements exactly twice.

@ankitasinha9912 2 жыл бұрын

How is the better approach O(2N) and not O(N^2).It has a nested while loop which increments the left pointer.

@monikaraut5266 2 жыл бұрын

Yes, I too think the same

@priyanksinha8152 Жыл бұрын

becuase the while loop is never running n times it will just run till there is no duplicate in the substring

@gaishiya7696 3 жыл бұрын

Very Well explained bhaiya!!!

@student_0224 Жыл бұрын

Understood thanks

@chittrakumari2549 2 жыл бұрын

Amazing Explaination 😀

@chandrashekharvichare8239 3 жыл бұрын

How do you solve using kadane's algo?can anyone provide solution?

@anujtripathi9457 2 жыл бұрын

nailed it!!

@jinhuang7258 Жыл бұрын

Understood.

@harshalgarg1149 2 жыл бұрын

Nice explanation.

@sonalisaxena22 3 жыл бұрын

Well Explained

@bhaveshkumar6842 2 жыл бұрын

Thank you so much bro!!!!!!!!

@sougatasingha9587 2 жыл бұрын

i am getting an error for "au" input the correct output should be 2 but my answer giving me 1 can't figure out the problem

@arvindroshaan8644 Жыл бұрын

Should the TC not be O(nlogn) as for each element we see if it is in a set? 10:09

@arvindroshaan8644 Жыл бұрын

It is actually O(nlog256)=O(n) as the maximum size of set is 256 (extended ASCII)

@sounakpramanick3932 3 жыл бұрын

Hello @Striver bhaiya, I want to ask that, is following the SDE sheet enough for coding rounds of companies ? I'm not talking of the coding interviews, I'm asking for the first online coding test which takes place in all the companies. Please reply, thank you.

@sundrammishra4757 3 жыл бұрын

Hi Sounak , I am quality assurance engineer working in a service based company. This SDE sheet is for those who have done basics of any programming language . You can go on hackerrank and there is a seprate block for interview preparation there are only 69 challanges if you will do them it would be sufficient to crack coding round.

@mickyman753 3 жыл бұрын

did you got any answer to your question ,if yes please share

@Dk-rf3zy 3 жыл бұрын

@take U forward bro if we want to print the string along with the length and if multiple print all then how can we approach? please help :)

@loserfruit9663 3 жыл бұрын

You can use substring function in between

@neuron8186 2 жыл бұрын

we can also we unordered hashmap as the insertion of char will less time and will be eff then this solution edit okay i should have watched the video first llol

@haramritsingh9522 Жыл бұрын

Understood !

@-Corvo_Attano 2 жыл бұрын

Thanks a lot :)

@NARUTOUZUMAKI-bk4nx 6 ай бұрын

Understood

@Onest_Coder Жыл бұрын

// class Solution { // public: // int lengthOfLongestSubstring(string s) { // vectormap(256,-1); // int left=0, right=0; // int n=s.size(); // int len =0; // while(right

@meenaldubey8570 2 жыл бұрын

great explanation

@G.V-wq4pl 10 ай бұрын

and isn't the first algorithm O(n^2) ?

@tarunraheja84 2 жыл бұрын

give code of all the approaches plz

@saketmehta6697 Жыл бұрын

Me set and queue use krke tezz bnn rha tha!! apne aukat yaad dila de! 2nd approach kudos!

@abhishekpattnaik8531 Жыл бұрын

Great explanation

@abdullahalmahfuj7623 Жыл бұрын

can anyone plz gimme the link of the docs?

@rishivijay523 3 жыл бұрын

I dont know hashing or hashmaps can you please tell me from where to learn them first?

@EntEduRealm 2 жыл бұрын

kzfaq.info/get/bejne/rK6KnbCc17nHYoE.html

@dailydestress6189 Жыл бұрын

understood

@mohitsingh7793 2 жыл бұрын

last approach gave tle on gfg submission

@jitenderyadav721 3 жыл бұрын

Thank you striver bhai

@nileshsinha7869 3 жыл бұрын

Great video 🔥🙏

@maxli9629 Жыл бұрын

Understooooooooooooooood!

@om_1_2 3 жыл бұрын

Thanks bro

@guptashashwat 2 жыл бұрын

Nice explanation

@BoostedPLAYER1 2 жыл бұрын

def LongestNonRepeatingSubString(string): resString = “” ansString = “” for char in string: if char not in resString: resString += char if len(ansString) < len(resString): ansString = resString else: resString = resString[resString.index(char) + 1:] + char return len(ansString)

@yeswanthh5068 Жыл бұрын

Understood sir

@mohitsaran9193 3 жыл бұрын

I didnt get why we use max(left, mpp[s[right]+1) instead of only mpp[s[right]+1......... plz explain, m stucked here only, apart this I understood everything

@manvikarya725 3 жыл бұрын

Because it is same as writing if(left

@prahaladsinghtomar3081 3 жыл бұрын

@@manvikarya725 he is asking as how mpp[s[right]]+1 can lie on left of left

@prahaladsinghtomar3081 3 жыл бұрын

try your code on "abba" you will find the reason

@subbucs5674 3 жыл бұрын

@@prahaladsinghtomar3081 I think it will be always left = mpp[s[right]] + 1, In the current window, left is left-most index. So, all elements in the current window will have their index >= left. Hence, it is not possible to have an element at left of left. Please correct me if I am wrong.