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.
@@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
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.
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
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
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.
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
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; } };
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 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()
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
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; }
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.
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.
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???
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.
How do you guys solving problems which need subscription to unlock.
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!!!!
After struggling... i solved this question by myself confidence++, Thank you striver
Thank you so much brother!!
was able to do this before watching the video all thank to you!!
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.
Thank you Striver! Was able to solve this question based on the understanding of the previous lecture
Solved before watching the video. watching now to see if i learn anything new.
thankyou so much Striver. i solved this question at my own just because of your previous lectures. you are amazing😍
How do you guys solving problems which need subscription to unlock.
Solved without watching video !!! Thank u striver ❤
How do you guys solving problems which need subscription to unlock.
Previous question is same to this one !!
lot of love from us striver ......... thank u so muchhhhh
public static int solution(String str,int k){
int n =str.length();
int maxLength =0;
for(int i=0;i
Similar as previous in last lec Understood ❤
I solved the question 😅 and then watching to get more idea ...little bit change of previous question....tryit guys then see the video❤
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
u should have taken some problem intead of this , becoz this has been previoulsly covererd
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
Notes are not available yet
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?
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.
Thank you very much
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
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 )
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.
understood
someone pls provide the full code. I am getting some of my testcases failed.
can i have the question link please?
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
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;
}
};
U erased mp[s[l]] u have to erase the value not tha frequency so mp.erase[s[l]] will be right
🎉❤
arigato
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;
}🎉❤
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()
please Striver make video on heaps
Solved it without watching the video
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
Same as Fruit In basket
Thank you so much Striver!!!!
🙄🙄🙄🙄 Am i the only one know that the L5 and L6 are same question
Yes, it's same
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
Can someone explain me how that "while" loop into a single "if" actually works and valid?
i didn't understand that
just watch lec 1 of this playlist if u have still doubt then do tell me
similar to approach in l5
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
Solved before watching video, the way you have planned the playlist is simply brilliant! Thank you Striver!!
Solved this 💕💕
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;
}
Its okay to opt with map it is much more intuitive...i feel but yeah vector is more good ofcourse😅
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 Striver!!!
"UNDERSTOOD BHAIYA!!"
Thank you sir for such an important series
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
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???
in every iteration every character visit maximum 2time so tc(2n)==0(n);
Understood. Thanks
Understood
thanks bhaiya
understood
god
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