L8. Longest Repeating Character Replacement | 2 Pointers and Sliding Window Playlist

Рет қаралды 105,990

Күн бұрын

Пікірлер: 120

@iam_bantu 7 ай бұрын

striver bro please upload the greedy playlist asap .. ur lectures are literally dominating all dsa premium courses.. far more better than anyone

@raghavmanish24 5 ай бұрын

it's been already uploaded

@lonerider6695 4 ай бұрын

bantu bhai ko ram ram

@kamalakannanng4206 7 ай бұрын

Striver - The G.O.A.T of DSA 💥

@prasun1595 4 ай бұрын

dude from 2n to n , kudos to you cuz my mind aint gone beyond that!

@thanhn2001 2 ай бұрын

I like how you go through the naive solution as well and compare the time and space complexities to the optimized solution

@kapilrules 3 ай бұрын

Thank you brother. I understood it because of you !🙏

@ayaaniqbal3531 8 ай бұрын

After understanding the logic and without seeing the solution now i am able to code it myself. Thanks striver for making us understand this algorithm.😊

@kaushit 6 ай бұрын

Ok let's understand how much you really know the depth. give me pattern of all substring in ABC string with k=1.

@shibainu7500 6 ай бұрын

@@kaushit {"A", "B", "C", "AB", "BC"} hi hoga na ?

@akworld2739 6 ай бұрын

lagta hai jindgi tutorial dekte dekte nikal jayigi

@evilgame6197 6 ай бұрын

kasam s ...sala karne betho to ye kese krenge...bas yahi chlta h

@anandunique1472 5 ай бұрын

sahi kaha bhaiya😂koi qn sliding window me slove nahi ho raha he

@amitmehta2285 4 ай бұрын

@@anandunique1472 wahi sabse jyda aata hain 🤣

@rishujeetrai5780 4 ай бұрын

mt dekho tutorial.. khud se code likho fir socho kya glt h. Key Tip: Dry Run your code with pen and paper. At last, kch smjh na aae to tutorial dekho approach smjhne k liye bs.

@Bhalu-kl7sq 4 ай бұрын

@@rishujeetrai5780 mein to aise kr raha tha pehle video solution dekho then khud try karo

@paragroy5359 6 ай бұрын

Last 5 minutes are very precious, it is a must watch. That trick could be used in other questions as well for optimisation.

@rushidesai2836 3 ай бұрын

That he has been mentioning in his previous videos as well.

@nirmalgurjar8181 6 ай бұрын

Trick is we dont want to minimize our max freq variable to get better result, ie. if we get result for max freq 3 we will continue to look for max freq greater than 3 if it exists and ignore freq less than equal 3. This will eliminate need of freq map scan and also remove while loop if we want to look for better max length.

@SarvanSuthar-d1p 6 ай бұрын

thanks bhaiya,now i got it.

@SoRandominfo 5 ай бұрын

Thanks a lot bro

@madhvishrivastava3646 4 ай бұрын

Bro when you explain it becomes so easy to understand.. Thank you so much :)

@rajharsh3739 7 ай бұрын

Bhaiya I am very much Greedy for your Greedy Playlist So when you are uploading that ?? 🙌🙌🤑🤑

@tejasjaulkar9658 7 ай бұрын

yes we want greedy playlist bhaiyyaa

@dhruvmishra9781 7 ай бұрын

same bro plz give greedy playlist after this much needed

@pailatejeswararao4572 5 ай бұрын

Thankyou very much man.I have watched 6 videos and solved this solution optimally by my own.I will learn everything from you 🙂

@qureekumari1324 11 күн бұрын

class Solution { public int characterReplacement(String s, int k) { int maxFreq=0, maxLen=0, l=0, r=0; int hash[]=new int[26]; while(rk){ hash[s.charAt(l)-'A']--; //Line Number - 9 l++; } maxLen=Math.max(maxLen,r-l+1); r++; } return maxLen; } } in the Video he has mentioned at the Line number 9 , hash[s.charAt(r)-'A']--; but above solution worked for me in Java, Anyway Thanks for the Logic Explanation

@az-zm4ji 5 ай бұрын

First solution witout optimization: class Solution { public: int characterReplacement(string s, int k) { //FML int l = 0, r = 0, ans = 0, maxf = 0; unordered_map umap; while(r < s.length()){ char c = s[r]; if(umap.find(c) == umap.end()) umap.insert({c, 1}); else umap.find(c)->second++; maxf = max(maxf, umap.find(c)->second); while(r - l + 1 - maxf > k){ umap.find(s[l])->second--; for(auto x : umap){ maxf = max(maxf, x.second); } l++; } ans = max(ans, r - l + 1); r++; } return ans; } };

@stith_pragya 7 ай бұрын

UNDERSTOOD....Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@raghavmanish24 5 ай бұрын

you are the legend for dsa ......thanks again striver

@user-nm2wc1tt9u 5 ай бұрын

Optimal: class Solution { public: int characterReplacement(string s, int k) { int n = s.size(); int left = 0, right = 0, maxFreq = 0, maxLen = 0; int hash[26] = {0}; while(right maxFreq){ maxFreq = hash[s[right]-'A']; }; if((right-left+1)-maxFreq > k){ //trimming the left portion hash[s[left]-'A']--; left++; } maxLen = max(maxLen, right-left+1); right++; } return maxLen; } };

@beinginnit 4 ай бұрын

Though this code runs gets accepted in LC, but i think something is missing: if((right-left+1)-maxFreq > k){ //trimming the left portion hash[s[left]-'A']--; left++; } what if my maxFreq was from i part and also contributing, here i need to recalculate the max freq. I may be wrong but this is what i think.

@nadellahridayesh3571 4 ай бұрын

@@beinginnit Yeah,I see that,but it neetcode channel also he explained in this way to optimize more to O(1) space like this,please have a look at it and explain

@sahilsukhdeve4695 5 ай бұрын

Java Code for java language forks class Solution { public int characterReplacement(String s, int k) { int n=s.length(); int maxlen=0,maxf=0; int i=0,j=0; Mapmap=new HashMap(); while(jk){ char ch2=s.charAt(i); map.put(ch2,map.get(ch2)-1); //decrement the frequency i++; } // if((j-i+1)+maxf

@urrahman196 2 ай бұрын

19:50 - why no need to decrease the maxFreq when frequency of any char in the map decreases

@aloklaha8694 2 ай бұрын

Thanks Striver. I was stuck on what will be the terminating condition for trimming down from left.

@amitgundoba9575 2 ай бұрын

Guys here is an simple code :----- class Solution { public: int characterReplacement(string s, int k) { int l=0,r=0,maxlen=0,maxfreq=0; int map[26]; fill(map,map+26,0); int n=s.length(); while(rk){ map[s[l]-'A']--; l++; } if(r-l+1-maxfreq

@KrishnaChauhan-fo4ky 23 күн бұрын

class Solution { public: int characterReplacement(string str, int l) { int s=0,k=0,longest=0,maxfreq=0;//str consists of only uppercase letters int mpp[26]; while(k

@hashcodez757 2 ай бұрын

#UNDERSTOOD

@sahilshinde3724 7 ай бұрын

You are writing it in very very small font can u please write which could be visible properly ! Thanks

@paragroy5359 6 ай бұрын

keep on making such videos, thanks a lot Great Content

@ShahNawaz-cx3pi 5 ай бұрын

C++ Leetcode solution: class Solution { public: int characterReplacement(string s, int k) { int n = s.size(); int l = 0; int r = 0; int ans = 0; int hash[26]={0}; int maxFre = 0; while(rmaxFre){ maxFre = hash[s[r]-'A']; } if((r-l+1)-maxFre>k) { hash[s[l]-'A']--; l++; } ans = max(ans, r-l+1); r++; } return ans; } };

@AradhyaSingh-un8di 2 ай бұрын

bro rigorously waiting for your heap playlist.. pls pls pls plss upload asap..

@shreyxnsh.14 Ай бұрын

My solution: int characterReplacement(string s, int k) { // s consists of only uppercase English letters. int maxlen = 0, maxf = 0; int l = 0, r = 0; unordered_map mpp; while(r < s.size()){ mpp[s[r]]++; maxf = max(maxf, mpp[s[r]]); int changes = (r-l+1) - maxf; if(changes > k){ char ch = s[l]; mpp[s[l]]--; if(mpp[s[l]]==0) mpp.erase(s[l]); l++; } maxlen = max(maxlen, r-l+1); r++; } return maxlen; }

@adarshmv261 6 ай бұрын

Please upload the code.. And looking forward for Heaps playlist please. Nowhere in youtube heaps problems are covered.. Please do it 🙏🏼🙏🏼🙏🏼🙏🏼 . It's being asked in interviews many times

@shashankvashishtha4454 4 ай бұрын

O((n + n)) logic is failing on AABABBB, we cannot because of the while loop directly jump to a point where some ans is missed out, if we write if instead of while (like in logic 3) then it will work.

@devgarg4331 7 ай бұрын

Bhaia will not the time complexity be N + 26(N) = 27N ??

@psinity 5 ай бұрын

i agree

@tejaswaniguttula5961 7 ай бұрын

Hi anna....!!! I am super excited with your sliding window protocol series. I understood every video till now in this series except this video with the difference between only if condition and inner while loop and its inner for loop. Could you please elaborate it in depth with some specific examples. So, that I can understand the thought process behind it. Please please anna...😊😊😊

@nirmalgurjar8181 6 ай бұрын

@Aryan-rb3yk 5 ай бұрын

@@nirmalgurjar8181 aaah i get it now ,thanks i got the 26 for loop part , but not the inner while loop part

@oyeesharme 3 ай бұрын

it was quite tough but understood bhaiya

@mradulmaheshwari9353 7 ай бұрын

Even if you don't update the maxfreq in while loop of left then also it is working smoothly. Although thanks for wonderfull series striver . code - class Solution { public int characterReplacement(String s, int k) { int[] hash=new int[26]; int maxlen=Integer.MIN_VALUE; int maxfreq=Integer.MIN_VALUE; int l=0; int n=s.length(); for(int r=0;rk){ char cl=s.charAt(l); hash[cl-'A']--; l++; } maxlen=Math.max(maxlen,r-l+1); } return maxlen; } }

$@fractionofinfinity842$

@fractionofinfinity842 6 ай бұрын

Why would this work? Also once let's say maxfreq is 3 because of 'A', and then if we remove 'A' from the window how do we update maxfreq from 3 to 2 assuming no other char having freq 3?

@Dsa_kabaap 6 ай бұрын

@@fractionofinfinity842actually we don't need to update the maxf value to the lesser value . Becz if u update it to lesser value like 2 , again it will come under > k while condition .

@Rahul_Mongia 5 ай бұрын

use if (r-l+1-maxf>k) rather than while

@dhruvdangi8923 5 ай бұрын

sir what a video this is just amazing 🙏🙌🙌🔻

@KshitijTakarkhede 4 ай бұрын

Hey peeps , I didn't get "while loop removing to if" can you please elaborate ( it will help alot)

@frameflickers500 15 күн бұрын

Why I'm not able to understand the time complexity ? There is nested loop but still it is not O(n^2). Why?

@Ultra_InstinctBit.h 5 ай бұрын

can we use use mapping for frequency calculations?

@TARUNRAO-oe8bm 5 ай бұрын

Striver bhaiya, I didnt understand why didnt we update the maxf when we are incrementing l. because the max trip will also change right when we change shorten the length of the subarray from front?

@sparksfly4421 4 ай бұрын

you're talking about his most optimal approach, i presume. In that case he didn't modify the maxfreq variable under the inner while loop because we don't need a maxfreq variable less than the current maxfreq variable regardless of the trimmed down substring we have right now. that's because, say, the current length of the substring is lesser but we still have the maxfreq value pertaining to the previous valid substring; in this case we simply would not require to have to check the length and change the consequent letters, we'd just ignore it. And to optimize it further, instead of looping through the letters till we get the valid window of (current_length - max_freq) > k, we could replace it with 'if' to check the condition only once because we can again simply ignore the additional trouble of having to loop through for each invalid checks which striver explains why in the other videos of his

@oyeesharme 3 ай бұрын

@@sparksfly4421 thanks bhai

@dayashankarlakhotia4943 7 ай бұрын

public int characterReplacement(String s,int k){ int[]freq=new int[26]; char[]ans=s.toCharArray(); int n=ans.length,l=0,max=0; for(int r=0;r

@psinity 5 ай бұрын

19:20 the time complexity should be O( N + N*26) right?

@sakshamsharma3156 5 ай бұрын

yes

@ugthesep5706 4 ай бұрын

Did all the questions of sliding windows by myself with the optimal solutions. Just leaving the fruit in basket one. Watch the video to know all the possible ways of solving that particular problem ;> Easy Peasy Lemon Squeezy 😅

@rohang7059 Ай бұрын

Can u give the link plz?

@ugthesep5706 Ай бұрын

@@rohang7059 which problem solution link?

@abubacker737 27 күн бұрын

can anyone explain how assigning mxfreq = 0 and finding maxfreq in further elements will be help?

@forfun8659 2 ай бұрын

Wow good question and nice explanation

@anandpandey918 2 ай бұрын

//Bruteforce Approach class Solution { public int characterReplacement(String str, int k) { int maxLength = 0; for (int start = 0; start < str.length(); start++) { for (int end = start; end < str.length(); end++) { String substring = str.substring(start, end + 1); int numChangesNeeded = substring.length() - getMaxFrequency(substring); if (numChangesNeeded > k) { break; } maxLength = Math.max(maxLength, end - start + 1); } } return maxLength; } private int getMaxFrequency(String str) { int[] freqArray = new int[26]; int maxFreq = 0; for (int i = 0; i < str.length(); i++) { freqArray[str.charAt(i) - 'A']++; } for (int frequency : freqArray) { maxFreq = Math.max(maxFreq, frequency); } return maxFreq; } } //Improved Approach class Solution { public int characterReplacement(String str, int k) { int maxLength = 0; int[] freqArray = new int[26]; for (int start = 0; start < str.length(); start++) { for (int end = start; end < str.length(); end++) { for (int range = start; range k) { break; } maxLength = Math.max(maxLength, (end - start + 1)); } } return maxLength; } private int getMaxFrequency(int[] freqArray) { int maxFreq = 0; for (int frequency : freqArray) { maxFreq = Math.max(maxFreq, frequency); } Arrays.fill(freqArray, 0); return maxFreq; } } //Good Approach class Solution { public int characterReplacement(String str, int k) { int maxLength = 0; int[] freqArray = new int[26]; for (int start = 0; start < str.length(); start++) { for (int end = start; end < str.length(); end++) { freqArray[str.charAt(end) - 'A']++; int numChangesNeeded = (end - start + 1) - getMaxFrequency(freqArray); if (numChangesNeeded > k) { break; } maxLength = Math.max(maxLength, (end - start + 1)); } Arrays.fill(freqArray, 0); } return maxLength; } private int getMaxFrequency(int[] freqArray) { int maxFreq = 0; for (int frequency : freqArray) { maxFreq = Math.max(maxFreq, frequency); } return maxFreq; } } //Better Approach class Solution { public int characterReplacement(String str, int k) { int maxLength = 0, maxFreq = 0, start = 0, end = 0; int[] freqArray = new int[26]; while (end < str.length()) { freqArray[str.charAt(end) - 'A']++; maxFreq = Math.max(maxFreq, freqArray[str.charAt(end) - 'A']); if ((end - start + 1) - maxFreq k) { freqArray[str.charAt(start) - 'A']--; maxFreq = 0; for (int i = 0; i < 26; i++) { maxFreq = Math.max(freqArray[i], maxFreq); } start++; } end++; } return maxLength; } } //Further Optimised class Solution { public int characterReplacement(String str, int k) { int maxLength = 0, maxFreq = 0, start = 0, end = 0; int[] freqArray = new int[26]; while (end < str.length()) { freqArray[str.charAt(end) - 'A']++; maxFreq = Math.max(maxFreq, freqArray[str.charAt(end) - 'A']); if ((end - start + 1) - maxFreq k) { freqArray[str.charAt(start) - 'A']--; start++; } end++; } return maxLength; } } //Optimal Approach class Solution { public int characterReplacement(String str, int k) { int maxLength = 0, maxFreq = 0, start = 0, end = 0; int[] freqArray = new int[26]; while (end < str.length()) { freqArray[str.charAt(end) - 'A']++; maxFreq = Math.max(maxFreq, freqArray[str.charAt(end) - 'A']); if ((end - start + 1) - maxFreq k) { freqArray[str.charAt(start) - 'A']--; start++; } end++; } return maxLength; } }

@torishi82 6 ай бұрын

Awesome brother. Understood.

@abhaysolanki4417 Ай бұрын

thanks for this

@AnjanaOuseph 6 күн бұрын

Where can I find the python codes for this problem?

@saketjaiswalSJ 7 ай бұрын

hacker as always thanks bro

@santasanthosh2113 2 ай бұрын

brilliant

@ramakrishnakcr4417 7 ай бұрын

understood

@sachinkumarsharma6483 3 ай бұрын

class Solution { public: int characterReplacement(string s, int k) { int n = s.size(); int l=0,r = 0,maxf = 0,maxlen = 0; mapmpp; while(rk) { mpp[s[l]]--; l = l+1; } maxlen = max(maxlen,r-l+1); r++; } return maxlen; } };

@tarunkr4698 3 ай бұрын

mera ho gya hai dimag kharab iss question se

@mansisethi8127 6 ай бұрын

I didn't understand , why we are doing maxf=0 in the else part. Can someone please explain ?

@Aryan-rb3yk 5 ай бұрын

I guess he did it initially as we was going to check again for the max freq using that 0-26 for loop its not in else everything is in if I guess

@everydaycodingwithgiyusama6949 6 ай бұрын

Is the naive or brute force code work properly for all test cases ? IF YES CAN ANYONE FIND ERROR IN MY CODE because It does not satisfy test case 2 of leetcode int[] arr = new int[26]; int maxc = 0; int maxl = 0; for(int i = 0; i< s.length();i++){ for(int j = i ; j < s.length() ; j++){ arr[s.charAt(j) - 'A']++; maxc = Math.max(maxc,arr[s.charAt(j)-'A']); if( (j - i + 1 ) - maxc

@ayushgakre9450 6 ай бұрын

int[] arr = new int[26]; should be after first loop bcz in next iteration is should be updated to 0

@AkshatMehra-l4b 7 ай бұрын

Great bro !

@sibiranganath 2 ай бұрын

Understood

@kiranchavan2632 4 ай бұрын

Where i can find sudo code?

@KartikeyTT 5 ай бұрын

ty sir

@ananttripathi6190 6 ай бұрын

why we are doing " -'A' " in hash[S[r]-'A' ????

@parahunter1650 6 ай бұрын

S[r]-'A' will give a integer value which we will use for indexing in our hash map For example if s[r]=B So, 'B'-'A'(i.e 66-65(ASCII VALUES OF B AND A) =1) So hash[1] will increase

@shashankvashishtha4454 4 ай бұрын

int window3(string& s,int k){ //O(n) most optimal pure O(n) logic int i=0; int j=0; int len=0; int max_freq=0; vectorfreq(26,0); while(j < n){ freq[s[j] - 'A']++; max_freq = max(max_freq,freq[s[j] - 'A']); if((j-i+1) - max_freq > k){ freq[s[i]-'A']--; i++; // max_freq = 0;//use less //max_freq = *max_element(freq.begin(),freq.end());//it will make no sense to calculate max freq here in if part we will get max in next iteration with line: max_freq = max(max_freq,freq[s[j] - 'A']); }else{ len = max(len,j-i+1); } j++; } return len; } this is most optimal logic, max_freq = 0, logic not clear to me and it is even not working with while version of this function, but this one is intuitive and clear.