Longest Substring With K Unique Characters | Variable Size Sliding Window
Vložit
- čas přidán 5. 09. 2024
- Become a Competitive Programming Hero with this structured batch to help all levels of programmers sharpen their skills: unacademy.cc/AVBAT
[FREE] Beginners lessons in programming by Codechef: unacademy.com/...
Patreon Link: / adityaverma
Video Pdf Notes And Code: / 45213007
Playlist Link: • Sliding Window Algorit...
Problem Description: practice.geeks...
Given a string you need to print the size of the longest possible substring that has exactly k unique characters.
Example:
Input:
2
aabacbebebe
3
aaaa
1
Output:
7
4 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Lets vote for Backtracking
koi faida nhi aditya verma bebafa hai XD
Sahi kha
@@raviashwin1157 free mein karrha hai usme bhi dikkat lmao
Moon-policy kahte hai shayad
Yep
First time,I m feeling confident to solve questions related to subarray .I m really blessed to find your channel.Thankyou so much sir!
Instead of erasing each entry when it gets 0 we can also use the approach he has used for count of anagrams. The idea of storing a count of distinct characters is a really useful one whenever we want to get an idea of characters to be taken into account WITHOUT acutally travelling the map or making some modifications.
Here's what you were thinking of:
int longestKSubstr(string s, int k) {
int n=s.size();
unordered_mapm;
int i=0;
int j=0; int dist=0; int ans=-1;
while(j
You meant this approach
const str = 'aabbvxbbc';
function longestSubstringWithKUniqueChar(str, k) {
let [start, end, res, count, obj] = [0, 0, 0, 0, {}];
while (end < str.length) {
if (!obj.hasOwnProperty(str[end])) {
count++
}
obj[str[end]] = (obj[str[end]] || 0) + 1;
if (count > k) {
while (count > k) {
obj[str[start]] = obj[str[start]] - 1;
if (obj[str[start]] === 0) {
delete obj[str[start]];
count--
}
start++;
}
}
if (count === k) {
res = Math.max(res, end - start + 1);
}
end++
}
return res
}
Please make a series for the XOR problems. We always see various tricky problems in contests. It will be very helpful.
ek hi solution he bro "PRACTICE" aur kuch nai hone vala
Managed to solve this problem without looking at the video because of the previous videos. Thanks for such an awesome playlist 🙌
same :)
same here
same here :D
Able to solve the problem before starting this video using prev concepts - count occurence of anagrams.
int longestKSubstr(string s, int k) {
// your code here
//We have identified that this problem is of Variable size sliding window
//string, substring, return window size with a given condition(window should contain k unqiue character and it should be
//longest)
//Here we can use hashmap to store the occurences of each characters
unordered_map mp;
int i=0, j=0; //for traversing the string
int mx = -1; // will store the longest substring with k unique characters
int count=0; //this variale will be used as to maintain our condition to find the mx
int n = s.size();
while(j
I just watched the first few lectures regarding the idea behind fixed size and variable size sliding window, and now i am solving problems on my own without checking the video out! Really helpful!
Here is my implementation for the above question:
simply applied the variable window template and used a frequency array to keep a track of the occurrences of each character.
int longestKSubstr(string s, int k) {
int n=s.size();
int i=0;int j=0;
vector freq(27,0);
int ans=-1;
while(jk){
freq[s[i]-'a']--;
if(freq[s[i]-'a']==0){
count--;
}
i++;
}
j++;
}
return ans;
}
After watching all the previous 9 videos, I am so happy that I was able to solve this problem all by myself. I followed the exact approach that you take while you solve the problems while explaining them in video.
Thanks a lot dude.
I had been struggling with DSA for quite some time now and finally I feel confident and all thanks to these videos of yours.
Same here ! Thanks
a bit extended shorter version, but understanding of the exhaustive version is must
mapmp;
int cnt = 0;
int start=0, end = 0;
int ans = -1;
while(end < s.size()){
mp[s[end]]++;
// distinct count check after add
if(mp[s[end]] == 1){
cnt++;
}
while(cnt > k){
mp[s[start]]--;
// distinct count count after remove
if(mp[s[start]]==0){
cnt--;
}
start++;
}
if(cnt == k){
ans = max(ans, end-start+1);
}
end++;
}
return ans;
thanks bro
is this code accepting all testcases, i tried it doesn't?
For future visitors here...This is the best explanation and playlist for this question and sliding window questions you need not to go anywhere else ...thora lengthy hai but dhyan dena coz dhyan hata toh smjh nhi aayega phir..myself watched this 3 times due to phone distraction :(( ..Aditya bhaiya you are best!!..Hopefully i get placed in a decent/good company ...
Mili koi company ?
@@prathamanand1037 same question
@@prathamanand1037 hnn trilogy xD
@@sahildalal1368 😂😂
@@kartiksrivastava3897 same question
For C++, we can use a vector instead of a map; 0th index of the vector will keep the count of 'a' and 26th will store the count of 'z'. Suppose we have characters 'a' and 'b' in our window. then the vector will have 24 zeroes; vector = {1,1,0,0,0,0....,0,0}. Then for each iteration will calculate 26-(count of zeroes in the vector) compare that to K.
Code below:
int longestKSubstr(string s, int k) {
vector cnt(26,0);
int ans = 0, i = 0, j = 0;
while(j
wow brother
i have solved this question on my own by just seen the video title and start doing solveing
Amazing part is that i have written exactly same code(word to word) as @Aditya sir .This shows the effort of aditya sir that how he explain in previous videos again and again, hats off to you sir
one week ago, I studied the sliding window algo and then solved 2-3 some easy ques of this algo but when i tried to solve a medium ques , i was not able to solve then i searched that problem in youtube and i found this video but before watching the sol of that problem , i prefered to watch your sliding window playlist first , and now after 3-4 days i solved this problem without watching the complete solution. ☺thanks a lot sir ❣
Was able to solve this problem without even watching the video. Thank You so much.
thanks sir, you explained the variable sliding format so well that I was able to solve the question on my own..
You are one of the best teacher ever met for understanding these interview questions!
starting 5s and ending 5s. Booster sound fills me with 200% energy 🧡😁
absolutely true.......
Awesome lecture as always.
if(hsh.size()==k) maxAns = max(maxAns, j-i+1);
Also add the above line (before the ending of the third case), to be on the safer side.
bro
Don't understand how it works even without this
this is the best I have ever seen some one explain this please continue this I was struggling for so long with sliding windows thank you
amazing intuition!!!! it was a hard question, which was asked in google interviews as per gfg!!! tysm for the explanation and crystal clear approach
True power of teaching is when your student solves the question only by watching the previous questions! 😉
Instead of using a map to count the occurrence of a character, we could use an array of size 26 and increase the count of the visited character. Space complexity would be constant even if the input string size becomes large. (Correct me if I am wrong, I am learning so any correction would be appreciated).
In the count array, if we are visiting the character first time (if the count of that char is 0), then we could increase the unique chars counter. If the counter > k, decrease the char count of left most char. If the char count of left most is 0, we decrement the counter by 1.
yes you can do it but using the map will reduce the time of writing so much of code for arrays
Even for map , your space is optimised as much as keeping an array of length 26
bhai bht hi accha smjhaya hai mai apne bootcamp me ise acche se smjh nhi paa rha tha but after watching your all video i feel much confident
Legend is back🔥
Btw ,Your old into music was fab ..!! Plz Continue with it🙏😁
@@ujjawal.pandey lol
By using for loop we will be able to get rid of those if condition. one which includes condition == k and another for condition < k.
In GFG, just take max=-1, rest everything Adi sir has taught is correct.
Farishte ho tum bhai 😂
Btw , thanks for this hint
Sir, in the last loop when the condition is greater than k then..after we increase i and remove calculations of i..we would have to calculate the ans first if the condition equals k..after that we would be increasing j..am i right?
Yes u r right!
// Longest Substring k unique character
/*
Given a string you need to print the size of the longest possible substring that has exactly
k unique characters.
Example:
Input:
2
aabacbebebe
3
aaaa
1
Output:
7
4 . */
#include
using namespace std;
int longest(string str,int k){
int i=0,j=0;
int maxi=INT_MIN;
int count=0;
unordered_map map;
map.clear();
while(jk){
map[str[i]]--;
if(map[str[i]]==0){
map.erase(str[i]);
}
i++;
}
j++;
}
}
return maxi;
}
int main()
{
string str;
cin>>str;
int k;
cin>>k;
cout
Shouldn't there be an 'if' condition if(map.size() == k){ maxi = max(maxi, j - i + 1) after the i++ in the last 'else-if' condition ? Like this :------
#include
#include
#include
using namespace std;
int longestSubstr(string s, int k)
{
int i = 0, j = 0, maxlen = INT_MIN;
unordered_map mp;
while (j < s.length())
{
// Calculations
mp[s[j]]++;
int count = mp.size(); // Condition
if (count < k)
{
j++;
}
else if (count == k)
{
maxlen = max(maxlen, j - i + 1);
j++;
}
else
{
while (count > k)
{
mp[s[i]]--;
if (mp[s[i]] == 0)
{
mp.erase(s[i]);
}
i++;
if (count == k)
{
maxlen = max(maxlen, j - i + 1);
}
}
j++;
}
}
return maxlen;
}
int main()
{
string str = "aabacbebebe";
int k = 3;
cout
2 mins into the video coded it myself .Awesome explanation sir
Sir g , aap hi mere guru hai🙏🙏. Thank u very much for your priceless teaching❤️❤️. Backtracking bhi padha dijiyega jldi se.
Java Code for the question:
Approach:
1. Keep on building the substring from j=0 [increasing the window size] and log occurance of each character in a Map.
2. If map size (Unique Characters in Map) becomes greater than k, keep on reducing window size (increase i pointer) and decrease the occurance of character from Map till map size becomes
correct, thanks
Sir aap pls graph ka bhi daalna ...
In GFG, just take ans=-1 Because if you didn't find any valid subarray with sum then ans remains -1
but if you take ans = INT_MIN and if you didn't find any valid subarray then it will remains ans INT_MIN and return
The format you provided and explained allow me to solve this question myself..
Thanks a lot;
One of the legend of competitive coding
Really bro hats off you 🎉❤
I am so happy to solve this without watching the solution. Thank you for this amazing series.
Solved it without watching the video....Thank u for such amazing teaching technique @adityaverma please leave a like
can u please share the code
@@shashankchaturvedi8697 i hope this would be helpful , solved it using java
public class LongestSubstringWithKUniqueChars {
static Map findUnique(char[] arr, int l, int r){
Map map = new HashMap();
int counter=0;
for(int i=l;i k){
while(map.size()>k){
map.put(arr[l], (int)map.get(arr[l])-1);
if((int)map.get(arr[l]) == 0){
map.remove(arr[l],map.get(arr[l]) );
}
l++;
}
r++;
}
}
System.out.println(max);
}
}
@@curtdudeanmol9393 nice code bro
👍👍
I added a check for if the no of unique chars in the string is less than the k.. for example Str=aaabe k =4
HashMap charMap=new HashMap();
int i =0;
int j =0;
int maxStringlen = Integer.MIN_VALUE;
while(jk){
if(charMap.containsKey(s.charAt(i))){
int freq=charMap.get(s.charAt(i));
freq--;
charMap.put(s.charAt(i),freq);
}
if(charMap.get(s.charAt(i))==0){
charMap.remove(s.charAt(i));
}
i++;
}
j++;
}
}
System.out.println("The no of unique chars are : " + charMap.size());
return (charMap.size()
Your channel is soo underrated.. Thankyou for such quality content
Easy Js approach of a similar question Leetcode problem 3:
function lengthOfLongestSubstring(s) {
let [start, end, ans] = [0, 0, 0];
let set = new Set();
if (s.length === 0) return ans;
while (end < s.length) {
if (set.has(s[end])) {
while (s[start] !== s[end]) {
set.delete(s[start]);
start++;
}
set.delete(s[start]);
start++;
ans = Math.max(ans, end - start + 1);
} else {
set.add(s[end]);
ans = Math.max(ans, end - start + 1);
end++;
}
}
return ans;
}
In the third condition map.size() > k after the while loop whose cond is run wgile loop until map.size()>k
when while loop terminate a condition occur map.size() == k which we are not considering and we have to take care of this condition
Superb explanation!!! I was struggling since a long time.
Java Code For Your Reference:-
Approach:
1. Keep on building the substring from j=0 [increasing the window size] and log occurance of each character in a Map.
2. If map size (Unique Characters in Map) becomes greater than k, keep on reducing window size (increase i pointer) and decrease the occurrence of characters from Map till map size becomes
are bhai yha pe jab cndn< k hoga tab bhi maxi = max(maxi,j-i+1) krna padega na
Another slight optimization-> whenever we move i to the next index, we can also increase j because when we get a candidate for a particular window size, increasing i and not j will only reduce the window size, leading to extra work. because the smaller window now will never be the ans to the problem
best explanation ever
Why not to use set ?
-> let's take string a a b a c b e b e be
When j is pointing to e that time set size will be 4 so we will erase the str[i] from set so 'a' will be erased from set . And but after that we will increment the i , now i is pointing to 'a' but in future when set size become greater than K that time we will remving str[i] that 'a' but now 'a' is not present in set so it will point to s.end() we will not able to move forward it is better to use map over set.
Can you re-explain it ? I didn't get it. Please explain why can't we use set & what are the advantages of using map in this particular problem.
Thanks
why dont we check m.size()==k in else part of m.size()>k...maybe while decrementing i, we can get size ==k again but while next iteration of j ,value gets incresed nd we miss that solution ??
In my opinion it's good to keep that statement in code but even if u not that doesn't change the answer becoz after removing however it will be having less size compared to previous one
While True:
Print ('Respect❤️')
IndentationError: ('unindent does not match any outer indentation level')
😂😂😂@@opera3846
We can store the count of unique characters in a variable and don't have to delete the entry from the map everytime count becomes zero. Below is the same C++ program:
int longestKSubstr(string s, int k) {
int i=0, j=0;
int n = s.length();
map mp;
int count = 0;
int ans = -1;
while(j
OR
we can skip the "count" variable altogether and decrement K whenever we encounter a distinct character. So whenever we have K < 0, we know that we have more distinct characters than required.
int longestKSubstr(string s, int k) {
int i = 0, j = 0, ans = -1;
unordered_map m;
for(j = 0; j < s.size(); j++){
if(!m[s[j]]++) k--;
while(k < 0)
if(--m[s[i++]] == 0)
k++;
if(k == 0)
ans = max(ans,j-i+1);
}
return ans;
}
@@noober7397 I don't mind creating one more variable as it doesn't impact the TC or SC .. just my opinion
ye to promotion bhi mast tareeke se karta hai :)
solving problem without watching video. Thanks for this awesome series.
Wao you made this question very easy. Thanks for making all these videos and helping us but just one suggestion. Don't repeat same thing again and again so many times because it might increase the time unnecessarily.
@Aditya Verma Sir, please make video on Binary Tree and backtracking
@23:11 marJava, MitJava (hindi) words by Aditya Verma.😂😂😂
When will your videos come on other patterns like pattern Two pointer, pattern Fast slow pointer, pattern cyclic sort and other patterns.
I can only see videos of pattern sliding window. :(
Eagerly waiting for other pattern videos.
Love your way of explanation. :)
@Aditya Verma how can we solve it for case of atleast or atmost???
Best explanation ever dada love from Kolkata ❤️,keep going dada and keep teaching us like this❤️❤️
I wrote this in MitJava and it worked successfully, Universal algo
finally solved the problem thank you sir
Explaination was awesome...❤🎉
@Aditya Verma Respect for you brother :)
Thank you so much! The video was very helpful 🙂
thanku bhaiya thanku so much, after struggling alot now i'm able to solve problem
Thanks @Aditya Verma
Java solution:
public int longestkSubstr(String s, int k) {
Map map=new HashMap();
int j=0;
int i=0;
int max=-1;
while (j < s.length()) {
map.put(s.charAt(j), map.getOrDefault(s.charAt(j), 0) + 1);
if (map.size() == k) {
max = Math.max(max, j - i + 1);
} else if (map.size() > k) {
while (map.size() > k) {
map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
if (map.get(s.charAt(i)) == 0)
map.remove(s.charAt(i));
i++;
}
}
j++;
}
return max;
}
Thankyou So much 😍 Very simple & Unique Explanation
Guyz C++ Code Solution:(Jisko Help leni hai yha se le sakta hai)
class Solution{
public:
int longestKSubstr(string str, int k) {
int i = 0, j = 0;
unordered_map mp;
int maxi = INT_MIN;
while(j < str.length()) {
mp[str[j]]++;
if(mp.size() < k) {
j++;
}
else if(mp.size() == k) {
maxi = max(maxi, j - i + 1);
j++;
}
else if(mp.size() > k) {
while(mp.size() > k) {
mp[str[i]]--;
if(mp[str[i]] == 0)
mp.erase(str[i]);
i++;
}
j++;
}
}
return maxi;
}
};
Have you solve the problem, longest substring with atleast k repeating character
Can you explain why using set was not adviced by Aditya Sir in the video ?
Thanks Aditya, very valuable series 🙌
Almost Solved the question without video i was just making mistake in while condition where i was not incrementing j
Amazing video
Understood :)
Solved before watching video using set and map, changed to only map after watching the video...
Sep'27, 2023 04:11 pm
Can you explain why using set was not adviced by Aditya Sir in the video ?
// Longest substring with K unique characters
int longestSubstringWithKUniqueCharacters(string str, int n, int k)
{
int i, j, res = INT_MIN;
map mp;
i = j = 0;
while(j < n)
{
mp[str[j]]++;
if(mp.size() == k)
res = max(res, j-i+1);
else if(mp.size() > k)
{
while(mp.size() > k)
{
mp[str[i]]--;
if(mp[str[i]] == 0)
mp.erase(str[i]);
++i;
if(mp.size() == k)
res = max(res, j-i+1);
}
}
++j;
}
return res;
}
In the last condition when unique characters are more than k ,
Do we need to have a check of the unique characters after doing i++, I think I we have to
Please correct me If I am wrong ,Providing the code snippet for reference.
while(j < s.length() ){
uc[s[j]]++;
if(uc.size() == k)
ans = max(ans, j-i+1);
else{
while(uc.size() > k ){
uc[s[i]]--;
if(uc[s[i]] == 0) uc.erase(s[i]);
i++;
if(uc.size() == k)
ans = max(ans, j-i+1);
}
}
j++;
}
Code in java:
class Solution {
public int longestkSubstr(String s, int k) {
HashMap map=new HashMap();
char ch[]=s.toCharArray();
int i=0,j=0;
int max=-1;
while(jk)
{
while(map.size()>k)
{
if(map.get(ch[i])>0)
{
map.put(ch[i],map.get(ch[i])-1);
if(map.get(ch[i])==0)
map.remove(ch[i]);
}
i++;
}
j++;
}
}
return max;
}
}
hii, I also code in java so rather than using HashMap cant we use HashSet for this problem ?
In str = "aabacbebebe", first max sub string is "aabacb" not "aabac" at 6:12
Can you start the backtracking playlist too. ..it will be helpful. .
On 20.25 , before moving j forward , dont we need to check if that cbe was the possible candidate or not??
How are you checking that?
Yes we have to do it
we need to check it
best teacher ever
Thank you very much. You are a genius.
Last else if condn. Mai hum while loop ke baad abar mp.size() == k ho jayega to use check nahi karenge?
I too had the same doubt because j++ is also done then what if next character increases the map size then one case will be lost
In the last while loop we are removing some elements from the window, therefore the size of window will definitely reduce from the current size and we've already taken care of the largest valid window size up to this position (in 2nd condition). So, even if mp.size() becomes equal to K in the last else if, then the window size will either be equal to or smaller than the current largest but not greater. Hence no need to check again.
@@sudeepchowdhary2577 thank u dude. That j++ was haunting me alot.
@@sudeepchowdhary2577 Yes you are right but in case of previous question we cannot do j++ in sum>k case. eg: ar=[1,1,1,1,4] and k=5 . Here we will go from k and miss [1,4] window.
@@sudeepchowdhary2577 if we have to print all substrings with k unique characters in that case we are lacking from the substring "cbe"
I have a doubt when the size of map is greater than k to after reducing the map size if the value become equal to k unique characters....in that case we have to check for maxlength there also right?
when size of map is greater than k, we go into the while loop and we come out of the while loop only when the size of the map(no. of unique characters) is k, so we check for the maxLength in this case only.
@Sameer Sahu ya bro we have to check this consition
If k=4 then we got some length n and when mapsize is greater than k so if we decrease then either length of another candidate will be n or less than n. So no need to check
Great lectures sir.
bhaiya, you explained very nicely. thank you. but, 0:55 🤣🤣🤣🤣. means data structure aata ho, but loops, conditionals ni.🤣🤣
Java, marjava, mitjava🤣🤣Op
BTW really good explanation!
javascript code
function longestSubstring(arr , k){
let i=0;
let j=0;
// assume there is no max at initial
let max = -1;
let hMap = new Map();
// iterate over the window
while(j
Should we need to check for mpp.size() == k in mpp.size() > k block as we may miss some potential answer after deleting i in the map??
yes we should
The explanation cannot be better.
class Solution {
public:
int longestKSubstr(string s, int k) {
// Your code goes here
int n = s.size();
int i = 0;
int j = 0;
int maxi = -1;
map mp;
while (j < n) {
mp[s[j]]++;
while (mp.size() >k) {
mp[s[i]]--;
if(mp[s[i]]==0){
mp.erase(s[i]);
}
i++;
}
if(mp.size()==k){
maxi=max(maxi,j-i+1);
}
j++;
}
return maxi;
}
};
Can I use the same approach if I have to find count of substrings with k different characters?
Solution in Python ::
def longest_sub(arr,k):
i,j = 0,0
n = len(arr)
dicty = {}
max_sub = 0
while(jk):
if arr[i] in dicty.keys():
dicty[arr[i]] -= 1
if dicty[arr[i]] == 0:
del dicty[arr[i]]
i+=1
j+=1
if max_sub==0:
return -1
else:
return max_sub
a =list("abcabcabcabcabcabcaba")
k = 2
print(longest_sub(a,k))
It would be nice if you turn on the cursor of the pointer or the pencil because I get lost in between whenever you scroll page or move to a different area
class Solution{
public:
int longestKSubstr(string s, int k) {
int n=s.length();
int i=0;
int j=0;
int count=0;
unordered_map mp;
mp.clear();
int res=0;
while(jk){
// reduce the frequency of the leftmost window character
mp[s[i]]--;
//if the frequency is 0 it does not exist in the window so we remove it from the map and reduce the unique element count
if(mp[s[i]]==0){
mp.erase(s[i]);
count--;
}
i++;
//if it hits the condition while removing unique elements then we update the result
if(count==k){
res=max(res,j-i+1);
}
}
j++;
}
}
return res==0? -1: res;
}
};
Did it without seeing the video , thanks to the previous video, any suggestions in the code will be appreciated
Just realized from a solutions and comments below that could have simply used map.size() instead of keeping that count, or could have kept the count instead of erasing
Java Solution According to this video and runs on gfg
class Solution {
public int longestkSubstr(String s, int k) {
HashMap hm=new HashMap();
int i =0;
int j =0;
int maxStringlen=-1;
while(jk && i
Bro ur code is not working for testcase: s="abcbdbdbbdcdabd"
K=5
Pls look into it
class Solution {
public int longestkSubstr(String s, int k) {
int j =0,i=0,msl=-1;
HashMap map=new HashMap();
while(jk && i< s.length())
{
// map.merge(s.charAt(i), -1, Integer::sum);
if(map.containsKey(s.charAt(i)))
{
map.put(s.charAt(i), map.get(s.charAt(i))-1);
}
if(map.get(s.charAt(i)) ==0 )
map.remove(s.charAt(i));
i++;
}
j++;
}
}
return (msl);
}
}
Runtime error : time limit exceed ... :| can you pls help !!!
code in java : import java.util.HashMap;
public class LongestSubstringWithoutRepeating {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) return 0;
HashMap map = new HashMap();
int left = 0, right = 0, maxLength = 0;
while (right < s.length()) {
char currentChar = s.charAt(right);
map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
while (map.size() > k) {
char leftChar = s.charAt(left);
map.put(leftChar, map.get(leftChar) - 1);
if (map.get(leftChar) == 0) {
map.remove(leftChar);
}
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
public static void main(String[] args) {
LongestSubstringWithoutRepeating solution = new LongestSubstringWithoutRepeating();
String s = "eceba";
int k = 2;
System.out.println(solution.lengthOfLongestSubstringKDistinct(s, k));
}
}
*Vote for Trees series by Aditya Verma!!!!*
I was trying to solve this question with set, but getting answer as 5, can anyone tell me what is wrong in this code.
private void findLongestSubString(String str, int k) {
int i = 0, j = 0, count = 0, left = 0, maxLength = 0;
Set set = new HashSet();
while (j < str.length()) {
if (set.contains(str.charAt(j))) {
left++;
j++;
} else {
set.add(str.charAt(j));
count++;
j++;
}
if (count < k) {
j++;
} else if (count == k) {
maxLength = Math.max(maxLength, count + left);
j++;
} else if (count > k) {
while (count > k) {
if (set.contains(str.charAt(i))) {
set.remove(str.charAt(i));
count--;
i++;
} else {
left--;
i++;
}
}
if (count == k)
maxLength = Math.max(maxLength, count + left);
j++;
}
}
System.out.println(maxLength);
}
if anybody uses python, then use defaultdict(int) instead of normal hashmap, as you will not be able to get size of normal hashmap
great teaching skills !
Big fan sir!!!! Autograph milega?
Java solution:
public static int findLength(String str, int k) {
if(str == null || str.length() == 0 || str.length() < k) {
throw new IllegalArgumentException();
}
int windowStart = 0, maxLength = 0;
Map charFrequencyMap = new HashMap();
// in this for loop, we look to extend the range [windowStart, windowEnd]
for(int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
char rightChar = str.charAt(windowEnd);
charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);
// shrinking the sliding window until we are left with 'k' distinct characters in the frequency map.
while(charFrequencyMap.size() > k) {
char leftChar = str.charAt(windowStart);
charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
// remove from the frequency map if the number of occurrences become '0'
if(charFrequencyMap.get(leftChar) == 0) {
charFrequencyMap.remove(leftChar);
}
windowStart++; // shrinks the window
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // remember the maxLength so far
}
return maxLength;
}
Another Java solution:
public static int findLongestSubstringEfficientSolution(String s, int k) {
if (s == null || s.length() == 0 || s.length() < k) {
throw new IllegalArgumentException();
}
Map frequencyMap = new HashMap();
int windowStart = 0, windowEnd = 0, maxLength = Integer.MIN_VALUE;
while (windowEnd < s.length()) {
// do calculations
char rightChar = s.charAt(windowEnd);
frequencyMap.put(rightChar, frequencyMap.getOrDefault(rightChar, 0) + 1);
if (frequencyMap.size() < k) {
windowEnd++;
} else if (frequencyMap.size() == k) {
// we calculate the window size and update any previous window length
maxLength = Math.max(maxLength, (windowEnd - windowStart + 1));
windowEnd++;
} else {
// Window size is greater than k, so we need to loop to decrement from the left
while (frequencyMap.size() > k) {
char leftChar = s.charAt(windowStart);
frequencyMap.put(leftChar, frequencyMap.get(leftChar) - 1);
if (frequencyMap.get(leftChar) == 0) {
frequencyMap.remove(leftChar);
}
windowStart++;
}
}
}
return maxLength;
}
What changes I can do for atleast k repeating character problem