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!!
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
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; }
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; } }
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.❤
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;
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
@@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.
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; }
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
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
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; } };
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++;
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; } ```
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
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++));
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
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?
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.
The new look of the DSA sheet and the whole website is just way too awesome sir.
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
Need such type of teachers
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
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!
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
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 ?
East and west striver bhaiya is best ❤❤
I think you haven't attached this youtube link in your take youforward site.
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
You are unstoppable... 🙏🙏 You are the best 🙏🙏
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 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;
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
public static void main( String[] args )
{
String s ="pwwkew";
String count ="";
int max =0;
int count1=0;
for(int i=0;i
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.
I Always love your explanation ❤
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
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❤
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
best explanation
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;
}
Thank you very much
Thanks Brother
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
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
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;
}
};
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;
}
nice explaination
Thanks❤
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
understood striver.....thanku
Thank you so much bro
NICE SUPER EXCELLENT MOTIVATED
One small addition to the code - the hashmap has to be updated with the location of the right pointer
why there is no code submision
understood bhaiya
Understood❤❤❤
Thanks. Understood.
Understood 😊😊
thankyou sir
Thank you so much
thank you bhaiii
Striverrrrrr❤❤❤❤❤🎉🎉
can we also do it with set ? instead of hashmap. what issue would it cause
Test Case failed on GFG: input = qwertyuioplkjh
output=13, correct output=14.
It will be more helpful if u submit in any coding platform
understood
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;
}
};
Can we do this longest substring without repeating characters problem using hashmap in Java?
Understood!
why do we need to do that range checking? I didn't understand
10:44
Understood.
Is this condition if (hash[arr[r]]
Thanku
this fails for the case abba, so we can update to l=max(l,v[s[r]]+1)
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".
solution in python:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
hashmap={}
left=0
right=0
Max=0
while(right
Helpfull
s= " " . why doesn't it clear this test case
use vector instead of array
Thank you for your explanation. it was nice.. I solved it.:)
Can we use map here ?
please upload string playlist
hy can anyone explain why strivers use hash array instead of the data structure
where to find the language specific code
can we use map here instead of hash array of 255 characters
But space complexity increases 😂
int lengthOfLongestSubstring(string s) {
int n=s.size();
int ans=0;
string a;
for(int i=0;i
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
Striver❤
Understood
❤❤❤
great
```
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;
}
```
Understood Sir!
Give running code
I did using binary search :(
Fucking Art bro , gg
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;
}
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?
❤
undersood
🙌🏻
👍
god
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
us
Please anyone can help me.. Why we use hash[256] ={0};
initially all possible 256 character's frequency is 0
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
Striver❤❤❤
understood
Understood
❤❤