L6. Longest Substring With At Most K Distinct Characters | 2 Pointers and Sliding Window Playlist

[@sindhunair3993]

Solved before watching video, the way you have planned the playlist is simply brilliant! Thank you Striver!!

[@rudrajitgupta3688]

Understood Striver. Was able to reuse the same code that was implemented in previous lecture before starting to watch the solution. Thank you again for such a great explanation

[@txbankush4601]

can u provide the full code. I am getting some of my testcases failed.

[@adarshshankarrai9912]

@@txbankush4601 int n,k; cin >> n >> k; string s; cin >> s; int l = 0, r = 0, maxlen = 0; mapmp; while(r < n) { mp[s[r]]++; if(mp.size() > k){ while(mp.size() > k){ mp[s[l]]--; if(mp[s[l]] == 0){ mp.erase(s[l]); } l++; } } if(mp.size()

[@SHARNAMKANSAL]

@@txbankush4601 int l=0,r=0,maxi=-1; unordered_mapmpp; while(rk) { mpp[s[l]]--; if(mpp[s[l]]==0)mpp.erase(s[l]); l++; } if(mpp.size()==k) { maxi=max(maxi,r-l+1); } r++; } return maxi;

[@shashankshekhar1713]

@@txbankush4601 for previous problem int totalFruits(int N, vector &arr) { int left = 0, right = 0, maxLength = 0; unordered_map map; while (right < N) { map[arr[right]]++; if (map.size() > 2) { map[arr[left]]--; if (map[arr[left]] == 0) { map.erase(arr[left]); } left++; } if(map.size()

[@harshpratapsingh2075]

@@txbankush4601 class Solution{ public: int longestKSubstr(string s, int k) { unordered_map m; for(auto it: s) m[it]++; if(m.size()

[@sunitsable2752]

Solved without watching video !!! Thank u striver ❤

[@Sankalp-sd6fm]

How do you guys solving problems which need subscription to unlock.

[@keerthishankar2341]

@@Sankalp-sd6fm search the problem in geeks for geeks and solve!

[@anishaa3298]

i was able to solve this by my own after watching first 2 mins of your video and previous lectures thank youuuuu!!!!! God bless

[@AKASHKUMAR-li7li]

After struggling... i solved this question by myself confidence++, Thank you striver

[@arnavshukla4271]

Thank you Striver! Was able to solve this question based on the understanding of the previous lecture

[@FutureForge-ir7xc]

Thank you so much Striver!!!!

[@AkshitChaudhary-vx8iw]

thankyou so much Striver. i solved this question at my own just because of your previous lectures. you are amazing😍

[@Sankalp-sd6fm]

How do you guys solving problems which need subscription to unlock.

[@AK-nj1je]

Actually the space complexity of the most optimal approach will be almost O(n) Coz just imagine all the elements are different then, the code will not care what's the size of the map, it will just keep adding elements in the map, howeven the maxlen will not be affected. Amazing lecture!!!!

[@vinaykumarratnala5832]

Solved before watching the video. watching now to see if i learn anything new.

[@tejasjaulkar9658]

lot of love from us striver ......... thank u so muchhhhh

[@harpreetnarwal6250]

Thank you so much brother!! was able to do this before watching the video all thank to you!!

[@gauravlandge3356]

I used to struggle a lot with sliding window Questions Thanks to u and your playlist because of which i am able to solve this type of Questions. Thankyou very much.

[@gourabrajak8132]

public static int solution(String str,int k){ int n =str.length(); int maxLength =0; for(int i=0;i

[@prateekshrivastava2802]

Previous question is same to this one !!

[@chrisliu657]

As an optimization to your solution, what if you tried storing the last index that each character appears in the dictionary? That way, when the # of distinct elements exceeds k, you shift i by the min value in your dictionary (which effectively skips over a certain character in the subarray). The only issue with this would be retrieving the min value. Great video btw!

[@shwetanshu13]

Thank you sir for such an important series

[@TheK_Fam]

One note here is that if the answer is not possible you would need to only update the max_len when len(ch_map) == k and initiate the max_len to be -1

[@Sankalp-sd6fm]

How do you guys solving problems which need subscription to unlock.

[@tanazshaik678]

this was available on code360

[@augustinradjou3909]

I solved the question 😅 and then watching to get more idea ...little bit change of previous question....tryit guys then see the video❤

[@14-a-akritiawasthi35]

bhaiya apne aap kiya hmne........................thankyou bhaiya

[@albert00991]

The space complexity of brute force should be O(K+1) because after that the break statement will get executed

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@LearnWithMe7777]

Similar as previous in last lec Understood ❤

[@Hello1234-vh5sm]

The code only considers the number of unique characters (map.size()) within the window to determine validity. However, for the problem of finding the maximum length of a substring with at most k replacements, we need to consider the frequency of the most frequent character within the window.

[@vivekrajput7400]

can you explain what exactly are you trying to say?

[@yaminisabbavarapu2538]

Actually not most frequent least or 2nd most frequent

[@racks8493]

i think your queestion's solution is in lecture - 8

[@tanujaSangwan]

Solved it without watching the video

[@joshl3013]

Very helpful. Liked and subcribed

[@augustinradjou3909]

Its okay to opt with map it is much more intuitive...i feel but yeah vector is more good ofcourse😅

[@KrishanKumar-lp2cd]

please Striver make video on heaps

[@Godlike_FTW]

Sir i am following ur course should i start with stack and queues(acc. To other yt channel) or start linklist i had completed till binnary search ❤❤❤

[@samagraagrawal5333]

Link list se start Karo. Stack and queue ke implementation mein link list ka use aayega

[@THOSHI-cn6hg]

u should have taken some problem intead of this , becoz this has been previoulsly covererd

[@gnanaphanideep6398]

Understood bro😁

[@dhruv7655]

Why not store the latest index of the character into the map instead of storing frequency? and once the condition fails, we can simply use an map iterator and find the min index stored in the map then just update L = ind + 1.

[@MdSarfrazcs]

l-5 same question where we have to care about two distinct element in this we have to think about k distinct element and nothing else

[@bunnysahith4810]

similar to approach in l5

[@hemantranjan2297]

Will bruter force run on string: "a" and k = 0, 1, 2

[@samsingh43]

it's better to use Vector rather than Hashmap

[@30sunique78]

Why ?

[@samagraagrawal5333]

​@@30sunique78 Hashmap works in logarithmic time , while vector/array/list in constant time Although if you are working in c++ there is also unordered map which works in constant time but still even then it is prefered to work with vectors as the constants involved with vector are better than hash maps

[@harshi993]

O(1) time complexity and only O(26) space

[@varenyabarve69]

We wont able to access this question, it's saying to view this question you must subscribe to premium 😢 . Now how to do that ?

[@anandraj3995]

do it on coding ninja

[@saatvikmangal7994]

@@anandraj3995 tysm bro

[@prateekshrivastava2802]

Gfg me same question h

[@shashankshekhar1713]

@@prateekshrivastava2802 link?

[@Dharmik_Vibes]

Same as Fruit In basket

[@shreyxnsh.14]

same as previous question

[@subee128]

Thank you very much

[@prathameshlendghar827]

Question in sheet is not correctly mapped with the video It expects to interchange any k char and by doing so find the longest string with same character and in the video it is changing all occurances of a distinct characters and for all instance of k different character.

[@Sahilsharma-sk5vr]

right

[@_sf_editz1870]

Solved this 💕💕

[@BhupeshReddy332]

Why was it O(256) space for brute force? because size is k distinct right? like as soon as size becomes k+1, we break. i didn't understand why so much extra space is being taken

[@lakshsinghania]

suppose the len of string is 256 containing all different characters and k = 256 then space will be O(256) he is writing everything in worst case thats like upper bound

[@jyotirmaysingh4059]

did this on my own

[@PIYUSHTAILORstillalive]

Could we use use queue to store char and the index of that character? The latest one and when size increases to 3 then we drop the front and take the latest index. Update the length and r keep on going. I just don't want that while loop running to find our l.

[@adityapundir5549]

I have one confusion that while optimizing the code we try to use 'if' instead of 'while' when we try to shift left pointer. But how does it optimize i am not getting. The iteration in both the cases will be exactly same, and i guess using while loop to shift left pointer is more efficient. Does anybody else have this confusion???

[@dayashankarlakhotia4943]

in every iteration every character visit maximum 2time so tc(2n)==0(n);

[@ajithshetty1684]

what happens when string is "AABABBA" Actual output will be 5 but current code will give 7, here k=2 means at max 2 times A to B conversion or vice versa can be done as per leetcode

[@ajithshetty1684]

Inputs & expected output from leetcode 1) Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. 2) Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.

[@ajithshetty1684]

But if this question is not linked to leetcode and the expectation is to find longest substring of k dinstinct characters then solution is perfect

[@DeadPoolx1712]

UNDERSTOOD;

[@oyeesharme]

thanks bhaiya

[@shashankpujari9970]

class Solution { public: int characterReplacement(string s, int k) { int n = s.length(); int l = 0, r = 0; map mp; int maxc = 0; while(r < n) { mp[s[r]]++; if(mp.size() > k) { mp[s[l]]--; if(mp[s[l]] == 0) mp.erase(s[l]); l++; } if(mp.size()

[@txbankush4601]

someone pls provide the full code. I am getting some of my testcases failed.

[@codeman3828]

Understood. Thanks

[@ManishKumar-dk8hl]

import java.util.HashMap; public class Solution { public static int kDistinctChars(int k, String str) { int l=0; int r=0; int maxlen=0; HashMapmpp=new HashMap(); while(r

[@aniketsingh5516]

not working

[@ibrahimalikhan3539]

@@aniketsingh5516 Correct this condition if(mpp.size() == k )

[@aditya_raj7827]

understood 😊😊

[@shreyaagarwal4320]

why is the TC roughly O(2n) ? it is while inside while right, so it should be O(n^2)

[@youcanyouwill2004]

n^2 happens only when for every constant j -> i runs till end, but here overall i runs only once and j also runs only once throughout the program. watch previous lecture striver has explained it

[@deepjoysarma7495]

can i have the question link please?

[@AJK-a2j00k4]

Hey, I didn't understand one thing, that he mentions extra TC O(log 256) where is this coming from? plus he is saying Space complexity as O(256) but there are only 26 alphabets right, then how is it 256 instead of 26? can someone plzz clarify this with detailed explanation or some video link/ references to understand this! Thank you

[@abhay3545]

There are 256 characters in any programming language, 26 (A-Z)+26(A-Z)+ special characters. The problem string can have any of the characters of 256.

[@AJK-a2j00k4]

@@abhay3545 ohh thnx

[@adityapandey23]

Understood

[@rlm3227]

understood

[@nikhilkumarpathak9588]

Notes are not available yet

[@giridharanpasupathi]

🙄🙄🙄🙄 Am i the only one know that the L5 and L6 are same question

[@spotshot7023]

Yes, it's same

[@chad._life]

why this code is not running anyone can tell me and correct it class Solution { public: int characterReplacement(string s, int k) { int r=0,l=0,maxlen=0,n=s.length(); unordered_mapmp; while(rk){ while(mp.size()>k){ mp[s[l]] = mp[s[l]]-1; if(mp[s[l]]==0){ mp.erase(mp[s[l]]); } l++; } } maxlen = max(maxlen,r-l+1); r++; } return maxlen; } };

[@nikhilbasir]

U erased mp[s[l]] u have to erase the value not tha frequency so mp.erase[s[l]] will be right

[@victorymindset-1]

Can someone explain me how that "while" loop into a single "if" actually works and valid? i didn't understand that

[@umangagarwal8726]

just watch lec 1 of this playlist if u have still doubt then do tell me

[@dayashankarlakhotia4943]

public int longestKSubstring(String s,int k){ int unique=0,len=-1,l=0; int[]freq=new int[26]; for(int i=0;ik){ ch=s.charAt(l)-'a'; freq[ch]--; if(freq[ch]==0) unique--; l++; } if(unique==k) len=Math.max(len,i-l+1); } return len; }🎉❤

[@angeldeveloper]

🎉❤

[@AkashKumarTiwary-u4b]

god

[@ashishpradhan6250]

arigato

[@p1xel3434]

public static int longestSubstringWithAtMostKDistinctCharacter(String str, int k) { int maxLength = 0; char[] chars = str.toCharArray(); int[] map = new int[26]; int uniqueChars = 0; int left = 0; int n = chars.length; for (int right = 0; right < n; right++) { if (map[chars[right] - 'a'] == 0) uniqueChars++; map[chars[right] - 'a']++; while (uniqueChars > k) { map[chars[left] - 'a']--; if (map[chars[left] - 'a'] == 0) uniqueChars--; left++; } maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }

[@RaghavN-rd5zw]

Thank you so much Striver!!!

[@SitaRam-m1i]

Understood

[@shashankvashishtha4454]

understood

[@tanazshaik678]

Understood

[@anshsaxena7297]

Understood