L6. Longest Substring With At Most K Distinct Characters | 2 Pointers and Sliding Window Playlist
HTML-код
- Опубликовано: 16 июл 2024
- Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.org/strivers-a2z...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/takeuforward
Thank you so much Striver!!!!
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.
can you explain what exactly are you trying to say?
Actually not most frequent least or 2nd most frequent
Thank you so much brother!!
was able to do this before watching the video all thank to you!!
lot of love from us striver ......... thank u so muchhhhh
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
can u provide the full code. I am getting some of my testcases failed.
@@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()
@@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;
@@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()
@@txbankush4601
class Solution{
public:
int longestKSubstr(string s, int k) {
unordered_map m;
for(auto it: s)
m[it]++;
if(m.size()
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!!!!
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.
thankyou so much Striver. i solved this question at my own just because of your previous lectures. you are amazing😍
Thank you sir for such an important series
Thank you very much
Understood. Thanks
Previous question is same to this one !!
Solved this 💕💕
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
I solved the question 😅 and then watching to get more idea ...little bit change of previous question....tryit guys then see the video❤
Similar as previous in last lec Understood ❤
Its okay to opt with map it is much more intuitive...i feel but yeah vector is more good ofcourse😅
similar to approach in l5
understood
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.
🎉❤
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 ❤❤❤
Link list se start Karo. Stack and queue ke implementation mein link list ka use aayega
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.
someone pls provide the full code. I am getting some of my testcases failed.
can i have the question link please?
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
not working
@@aniketsingh5516 Correct this condition if(mpp.size() == k )
We wont able to access this question, it's saying to view this question you must subscribe to premium 😢 . Now how to do that ?
do it on coding ninja
@@anandraj3995 tysm bro
Gfg me same question h
@@prateekshrivastava2802 link?
god
Same as Fruit In basket
arigato
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
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
it's better to use Vector rather than Hashmap
Why ?
@@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
O(1) time complexity and only O(26) space
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
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.
@@abhay3545 ohh thnx
why is the TC roughly O(2n) ?
it is while inside while right, so it should be O(n^2)
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
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
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.
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
🙄🙄🙄🙄 Am i the only one know that the L5 and L6 are same question
Yes, it's same
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.
right
Thank you so much Striver!!!