whenever I am looking for an explanation to a problem and I search it on youtube and if I don't find a solution by striver I get disappointed...Love from Flipkart!
I just cant express my gratitude in words towards this man . the way he simplifies every single thing makes everything appear so easy . I am so glad that I found this channel.
Hello Bhaiya!! From past few weeks i was not able to watch any of your videos. Was going through depression . But the moment i joined the journey again with you is a blessing. You have a different aura ....just looking at you i just simply forget everything and a new spark is ignited within me. Thank alot Bhaiya for your efforts and helping me!!
Hi Striver, I'm not sure if this comment will reach you or not, but I just want to say one thing: I've been watching your videos for more than a year now and have covered a huge part of the graph and dynamic programming playlists. Whenever I watch your videos, I really fall in love with your teaching style, and of course, your smile, and sometimes your small jokes. I enjoy your videos, and it feels like you're not just my tutor; it feels like you're someone very close to me, teaching me with fun and pleasure. However, in your recent playlists, I totally miss that. It feels like you're not as friendly anymore; you're just a teacher like any other tutor. Whenever I watch videos from this playlist, sometimes I wonder what happened to you. Why are you so quiet now? Why don't you joke around anymore? After all, I love your work; it's just my opinion.
@@rushidesai2836 lol, pay me 1 cr per annum, I am ready to take the stress lol, millions of middle class people are earning peanuts but still work with smile on their face just to support their families
1 fix in the brute force is that you need to fill the arrays with 0 every time youre moving i. so heres the correctedd brute.public int lengthOfLongestSubstring(String s) { int[] arr = new int[256]; int max = 0; int n = s.length();
for (int i = 0; i < n; i++) { // Reset the array for each new starting point Arrays.fill(arr, 0);
for (int j = i; j < n; j++) { // If character at j has been seen, break the loop if (arr[s.charAt(j)] == 1) { break; }
// Otherwise, add the character to substring int len = j - i + 1; max = Math.max(len, max); // Remember it arr[s.charAt(j)] = 1; } } return max; }
00:06 Finding longest substring without repeating characters 02:46 Using 2 Pointers for Substring Generation 04:59 Using hashing to find the longest substring without repeating characters 07:36 Optimizing algorithm using two pointers and sliding window approach 10:02 Understanding two pointer and sliding window approach 12:17 Determine longest substring without repeating characters using hashmap and sliding window 14:45 Updating characters in a sliding window to find longest substring without repeats. 17:06 Sliding window technique for finding longest substring without repeating characters. 19:10 Algorithm explanation and time complexity analysis 21:42 Explanation of sliding window algorithm with two pointer
int lengthOfLongestSubstring(string s) { if(s.size()==0)return 0; int i=0; int j=0; int maxi=1; int n=s.size(); unordered_mapmp; while(j=i) { i=mp[s[j]]+1; } maxi=max(maxi,j-i+1); mp[s[j]]=j; j++; } return maxi; } finally accepted. Thankyou Striver😊for your effort. i like and appreciate you from bottom of my heart.❤
Loved your explaination. Bhaiya instead of using a HashMap we can also use a Set. It will save some more memory. class Solution { public int lengthOfLongestSubstring(String s) { int i = 0, j = 0, max = 0; Set set = new HashSet(); while (j < s.length()) { if (!set.contains(s.charAt(j))) { set.add(s.charAt(j)); j++; max = Math.max(max, set.size()); } else { set.remove(s.charAt(i)); i++; } } return max; } }
Very,very smart case where left has to be the rightmost. eg checking in abc, if left is already at 4 and prior presence of b is at 2, we need not update left to 3, instead it should be max of prior instance+1,already present left
i think this is overcomplicating things. The easy code could be: int n = s.length(); int left = 0; int right = 0; int maxLen = 0; map mpp; int len=0; while (right < n) { if (mpp.find( s[right] ) != mpp.end() ) { left++; right=left; mpp.clear(); } else{ len++; mpp[s[right]] = right; maxLen=max(right-left+1,maxLen); right++; } } return maxLen;
with this solution we can make time complexity as O(n) and space complexity O(n) Set set=new HashSet();
int left=0; int right=0; int mxLen=0; String result = ""; while(rightmxLen) { mxLen= right- left +1; result=str.substring(left,right+1); } right++; }else { set.remove(str.charAt(left)); left++;
Hi @takeuforward , I am not getting language specific codes in your website also. In ur website it is showing coming soon. Would you please update the same if u have not updated
Time complexity-O(n) only ,no while loop, Check my solution int lengthOfLongestSubstring(string s) { unordered_map mpp; int count=0; int max=0; for(int i=0;i1){ count=min(i- mpp[s[i]].second,count); } mpp[s[i]].second=i; if(count>max){max=count;} } return max; }
for those who are struggling use memset to initialise hash array instead of normal initialization ``` int lengthOfLongestSubstring(string s) { int n = s.length(), maxlen = 0; int l = 0, r = 0; int hash[255]; memset(hash, -1, sizeof(hash)); while (r < n) { if (hash[s[r]] != -1 && hash[s[r]] >= l) { l = hash[s[r]] + 1; } hash[s[r]] = r; maxlen = max(maxlen, r - l + 1); r++; } return maxlen; } ```
class Solution { public: int lengthOfLongestSubstring(string s) { int l = 0; int r = 0; int maxlen = 0; map mpp; while (r < s.size()) { mpp[s[r]]++; while(mpp[s[r]]>1){ mpp[s[l]]--; l++; } maxlen = max(maxlen, r - l + 1); r++; } return maxlen; } };
@@NEUTRON-h5t when you find that there is a duplicate element, i.e. freq[s[j]] != 0, you start moving the i pointer till that duplicate element is removed from your window. By the time you reach 1 index ahead of the duplicate element, you would have removed the duplicate element. Again, do a dry run to better understand the logic.
with the above psuedo code, solved using hashmap: class Solution { public: int lengthOfLongestSubstring(string s) { map mp; int maxLen = 0; int n = s.size(); int l=0, r=0; while(r
int lengthOfLongestSubstring(string s) { unordered_mapmpp; int ans=0,i=0; int n= s.size(); int cnt = 0; if(s.size()==1){ return 1; } while(i!=n){ if(mpp[s[i]]==1){ ans = max(ans,cnt); cnt=0; mpp.clear(); } mpp[s[i]]++; cnt++; i++; } return ans; } //can anyone explain why it is failing the testcase of "au".
guys for input string having no repeating characters, i am getting wrong answer(one less than correct length) in leetcode for example input string="aus" ; the correct output is 3; but output from striver's optimal code is 2.Can someone help me out
Same situation mere sath thi kuch months pahle , but now I can solve even medium level questions easily , u just need practice, practice and more practice
public int lengthOfLongestSubstring(String s) { HashSetmp=new HashSet(); int i=0,j=0,max=0; while(j < s.length()){ if(!mp.contains(s.charAt(j))){ mp.add(s.charAt(j++));
This was actually my 2nd problem which i solved but later realised thst solution is not correct if input a string like this Abcbdefghik As i was using break at the first duplicate character 😅😅😅
whenever I am looking for an explanation to a problem and I search it on youtube and if I don't find a solution by striver I get disappointed...Love from Flipkart!
Bro you are a sde at flipkart?
@@arnabsarkar5245 no, he lives in flipkart
The new look of the DSA sheet and the whole website is just way too awesome sir.
I just cant express my gratitude in words towards this man . the way he simplifies every single thing makes everything appear so easy . I am so glad that I found this channel.
I solved it on my own! Your teaching is amazing bhaiya!!!
Hello Bhaiya!!
From past few weeks i was not able to watch any of your videos.
Was going through depression .
But the moment i joined the journey again with you is a blessing.
You have a different aura ....just looking at you i just simply forget everything and a new spark is ignited within me.
Thank alot Bhaiya for your efforts and helping me!!
Just hope for the better friend , I am gone through that🙂😀
Bhai abb Kasey ho tum dono. Student ho kyaa@@sahil_bagde
Hi Striver, I'm not sure if this comment will reach you or not, but I just want to say one thing: I've been watching your videos for more than a year now and have covered a huge part of the graph and dynamic programming playlists. Whenever I watch your videos, I really fall in love with your teaching style, and of course, your smile, and sometimes your small jokes. I enjoy your videos, and it feels like you're not just my tutor; it feels like you're someone very close to me, teaching me with fun and pleasure. However, in your recent playlists, I totally miss that. It feels like you're not as friendly anymore; you're just a teacher like any other tutor. Whenever I watch videos from this playlist, sometimes I wonder what happened to you. Why are you so quiet now? Why don't you joke around anymore? After all, I love your work; it's just my opinion.
yeh! i noticed it too! hoping he's doing good in life..
agree
Google's job is stressful buddy. It takes lot of effort jusy to make these videos.
@@rushidesai2836 lol, pay me 1 cr per annum, I am ready to take the stress lol, millions of middle class people are earning peanuts but still work with smile on their face just to support their families
@@parth_3856 with job in google everyone will do good in life
Need such type of teachers
East and west striver bhaiya is best ❤❤
Solved it on my own...came here to make notes :)
Thank you!
hi Striver,
Your Graph, DP, binary search playlist are amazing. Please create a playlist for String as well.
Binary Search was pretty good I agree!
1 fix in the brute force is that you need to fill the arrays with 0 every time youre moving i. so heres the correctedd brute.public int lengthOfLongestSubstring(String s) {
int[] arr = new int[256];
int max = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
// Reset the array for each new starting point
Arrays.fill(arr, 0);
for (int j = i; j < n; j++) {
// If character at j has been seen, break the loop
if (arr[s.charAt(j)] == 1) {
break;
}
// Otherwise, add the character to substring
int len = j - i + 1;
max = Math.max(len, max);
// Remember it
arr[s.charAt(j)] = 1;
}
}
return max;
}
can i use HashMap instead of hash Array since TC for searching in HashMap is also O(1)
@@SibiRanganathL yes sure!
can you please tell me why striver created hash for 256 size ?
00:06 Finding longest substring without repeating characters
02:46 Using 2 Pointers for Substring Generation
04:59 Using hashing to find the longest substring without repeating characters
07:36 Optimizing algorithm using two pointers and sliding window approach
10:02 Understanding two pointer and sliding window approach
12:17 Determine longest substring without repeating characters using hashmap and sliding window
14:45 Updating characters in a sliding window to find longest substring without repeats.
17:06 Sliding window technique for finding longest substring without repeating characters.
19:10 Algorithm explanation and time complexity analysis
21:42 Explanation of sliding window algorithm with two pointer
You are unstoppable... 🙏🙏 You are the best 🙏🙏
I think you haven't attached this youtube link in your take youforward site.
int lengthOfLongestSubstring(string s)
{
if(s.size()==0)return 0;
int i=0;
int j=0;
int maxi=1;
int n=s.size();
unordered_mapmp;
while(j=i)
{
i=mp[s[j]]+1;
}
maxi=max(maxi,j-i+1);
mp[s[j]]=j;
j++;
}
return maxi;
}
finally accepted.
Thankyou Striver😊for your effort.
i like and appreciate you from bottom of my heart.❤
Great bhaiji 🙏
I Always love your explanation ❤
Loved your explaination. Bhaiya instead of using a HashMap we can also use a Set. It will save some more memory.
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0, max = 0;
Set set = new HashSet();
while (j < s.length())
{
if (!set.contains(s.charAt(j)))
{
set.add(s.charAt(j));
j++;
max = Math.max(max, set.size());
}
else
{
set.remove(s.charAt(i));
i++;
}
}
return max;
}
}
In else part i think you should remove s.charat(j) not i
great bro thanks
It will take n^2 time
Thank you for this wonderful code
Explained very well... 💯💯
Very,very smart case where left has to be the rightmost. eg checking in abc, if left is already at 4 and prior presence of b is at 2, we need not update left to 3, instead it should be max of prior instance+1,already present left
i think this is overcomplicating things. The easy code could be:
int n = s.length();
int left = 0;
int right = 0;
int maxLen = 0;
map mpp;
int len=0;
while (right < n) {
if (mpp.find( s[right] ) != mpp.end() ) {
left++;
right=left;
mpp.clear();
}
else{
len++;
mpp[s[right]] = right;
maxLen=max(right-left+1,maxLen);
right++;
}
}
return maxLen;
public static void main( String[] args )
{
String s ="pwwkew";
String count ="";
int max =0;
int count1=0;
for(int i=0;i
vector< int > mpp(256,-1);
int l=0;
int r=0;
int maxlength=0;
while(r=l) l = mpp[s[r]] +1;
}
mpp[s[r]] = r;
maxlength = max(maxlength,r-l+1);
r++;
}
return maxlength;
Superb raj❤
With set
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n=s.size();
if(n==0) return 0;
int l=0,r=0;
int ans=1;
sets1;
while(r
with this solution we can make time complexity as O(n) and space complexity O(n)
Set set=new HashSet();
int left=0;
int right=0;
int mxLen=0;
String result = "";
while(rightmxLen) {
mxLen= right- left +1;
result=str.substring(left,right+1);
}
right++;
}else {
set.remove(str.charAt(left));
left++;
}
}
return result;
}
Hi @takeuforward , I am not getting language specific codes in your website also. In ur website it is showing coming soon.
Would you please update the same if u have not updated
why there is no code submision
nice video
best explanation
Is this condition if (hash[arr[r]]
Bhaiya wala code { BY USING MAP NAAM KI ARRAY } :--
class Solution {
public int lengthOfLongestSubstring(String s) {
int l=0;
int r=0;
int[] map=new int[256];
Arrays.fill(map, -1);
int maxlen=0;
while(r
Striverrrrrr❤❤❤❤❤🎉🎉
Understood❤❤❤
Time complexity-O(n) only ,no while loop, Check my solution
int lengthOfLongestSubstring(string s) {
unordered_map mpp;
int count=0;
int max=0;
for(int i=0;i1){
count=min(i- mpp[s[i]].second,count);
}
mpp[s[i]].second=i;
if(count>max){max=count;}
}
return max;
}
for those who are struggling use memset to initialise hash array instead of normal initialization
```
int lengthOfLongestSubstring(string s) {
int n = s.length(), maxlen = 0;
int l = 0, r = 0;
int hash[255];
memset(hash, -1, sizeof(hash));
while (r < n) {
if (hash[s[r]] != -1 && hash[s[r]] >= l) {
l = hash[s[r]] + 1;
}
hash[s[r]] = r;
maxlen = max(maxlen, r - l + 1);
r++;
}
return maxlen;
}
```
What is a memset?
Why does a normal intialization not work on this code?
@@suhanigupta2861 Have you got to know why? If yes please explain
@@Messi23485 No idea as of now
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int l = 0;
int r = 0;
int maxlen = 0;
map mpp;
while (r < s.size()) {
mpp[s[r]]++;
while(mpp[s[r]]>1){
mpp[s[l]]--;
l++;
}
maxlen = max(maxlen, r - l + 1);
r++;
}
return maxlen;
}
};
Bhaiya mene isko freq array banakar easy way me kardiya.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector freq(256, 0);
int i = 0, j = 0;
int maxi = 0;
int n = s.length();
while (j < n) {
if (freq[s[j]] == 0) {
freq[s[j]]++;
maxi = max(maxi, j - i + 1);
j++;
} else {
freq[s[i]]--;
i++;
}
}
return maxi;
}
};
bro can you explain me this code especially this part
else {
freq[s[i]]--;
i++;
@@NEUTRON-h5t when you find that there is a duplicate element, i.e. freq[s[j]] != 0, you start moving the i pointer till that duplicate element is removed from your window. By the time you reach 1 index ahead of the duplicate element, you would have removed the duplicate element. Again, do a dry run to better understand the logic.
Thanks Brother
Thank you very much
Thanks❤
Understood 😊😊
with the above psuedo code, solved using hashmap:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map mp;
int maxLen = 0;
int n = s.size();
int l=0, r=0;
while(r
understood striver.....thanku
NICE SUPER EXCELLENT MOTIVATED
Thank you so much bro
nice explaination
can we also do it with set ? instead of hashmap. what issue would it cause
Thank you so much
Test Case failed on GFG: input = qwertyuioplkjh
output=13, correct output=14.
One small addition to the code - the hashmap has to be updated with the location of the right pointer
thankyou sir
Thanks. Understood.
understood bhaiya
thank you bhaiii
Thank you for your explanation. it was nice.. I solved it.:)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length(), l = 0, r = 0, cnt = 0;
unordered_set seen;
if (n == 0)
return 0;
while (r < n) {
if (r < n && seen.find(s[r]) == seen.end()) {
seen.insert(s[r]);
cnt = max(cnt, r - l + 1);
r++;
} else {
seen.erase(s[l]);
l++;
}
}
return cnt;
}
};
why do we need to do that range checking? I didn't understand
Understood!
this fails for the case abba, so we can update to l=max(l,v[s[r]]+1)
Can we do this longest substring without repeating characters problem using hashmap in Java?
Understood.
It will be more helpful if u submit in any coding platform
Striver❤
Can we use map here ?
where to find the language specific code
Helpfull
hy can anyone explain why strivers use hash array instead of the data structure
understood
int lengthOfLongestSubstring(string s) {
unordered_mapmpp;
int ans=0,i=0;
int n= s.size();
int cnt = 0;
if(s.size()==1){
return 1;
}
while(i!=n){
if(mpp[s[i]]==1){
ans = max(ans,cnt);
cnt=0;
mpp.clear();
}
mpp[s[i]]++;
cnt++;
i++;
}
return ans;
}
//can anyone explain why it is failing the testcase of "au".
Thanku
can we use map here instead of hash array of 255 characters
But space complexity increases 😂
solution in python:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
hashmap={}
left=0
right=0
Max=0
while(right
Understood Sir!
guys for input string having no repeating characters, i am getting wrong answer(one less than correct length) in leetcode
for example input string="aus" ;
the correct output is 3;
but output from striver's optimal code is 2.Can someone help me out
its because you used array for hash use vector
@@Anandsingh-bu5nq thank you its working fine now;
changed int hash[256]={-1}
to vectorhash(256,-1)
@@bishalmahanta4398 what is the difference here between using vector and array?
please elaborate
s= " " . why doesn't it clear this test case
use vector instead of array
❤❤❤
Understood
please upload string playlist
great
int lengthOfLongestSubstring(string s) {
int n=s.size();
int ans=0;
string a;
for(int i=0;i
Fucking Art bro , gg
Give running code
❤
I did using binary search :(
Aise Q. Mere se nhi jamte basic jm jate 😢 plz koi batao how can i do ……
solve codeforces qs lots. ur programming and basic thinking will improve loads. solve prev contsets qs
@@obamaengineer4806 thank you I'll try to solve
Same situation mere sath thi kuch months pahle , but now I can solve even medium level questions easily , u just need practice, practice and more practice
@@Cityscapes411 WHICH PLATFORM U SOLVE FROM AND HOW MANY QS PER DAY AND ANY GENERAL TIPS?
🙌🏻
10:44
Anybody please give that code for java
public int lengthOfLongestSubstring(String s) {
HashSetmp=new HashSet();
int i=0,j=0,max=0;
while(j < s.length()){
if(!mp.contains(s.charAt(j))){
mp.add(s.charAt(j++));
max=Math.max(max,j-i);
}
else
{
mp.remove(s.charAt(i++));
}
}
return max;
}
undersood
```
int lengthOfLongestSubstring(string s) {
unordered_map mp;
int i, j, n = s.size(), length = INT_MIN;
i = j = 0;
while(j < n)
{
mp[s[j]]++;
if(mp[s[j]] == 1)
length = max(length, j-i+1);
while(mp[s[j]] > 1)
{
mp[s[i]]--;
++i;
length = max(length, j-i+1);
}
++j;
}
return length == INT_MIN ? 0 : length;
}
```
👍
god
Please anyone can help me.. Why we use hash[256] ={0};
initially all possible 256 character's frequency is 0
us
pata nhi ye kn log hai jinhe samjh aa raha hai. educated dikhne k lie english bole ja rahe jbki kisi ko bhi english me nahi samjh aata hoga India me
Sab gawar nahi hai
too long video
Beginners like me need such explanation. You also would have started from zero only
worst acche se code de doge to kya jayega bakwas explanation
This was actually my 2nd problem which i solved but later realised thst solution is not correct if input a string like this
Abcbdefghik
As i was using break at the first duplicate character 😅😅😅
Striver❤❤❤