L3. Longest Substring Without Repeating Characters | 2 Pointers and Sliding Window Playlist
ฝัง
- เผยแพร่เมื่อ 27 ม.ค. 2025
- Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.o...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/take...
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
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
I think you haven't attached this youtube link in your take youforward site.
East and west striver bhaiya is best ❤❤
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 ?
@@faysalahmedtarek8649 because in ASCII system there are 256 characters (this may be reason )
Solved it on my own...came here to make notes :)
Thank you!
You are unstoppable... 🙏🙏 You are the best 🙏🙏
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
Done on 22 Jan 2025 at 01:34
Place : Study Room 2 , Hostel 5 , IIT Bombay
Great bhaiji 🙏
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.❤
Explained very well... 💯💯
I Always love your explanation ❤
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 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 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
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;
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
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
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
Is this condition if (hash[arr[r]]
public static void main( String[] args )
{
String s ="pwwkew";
String count ="";
int max =0;
int count1=0;
for(int i=0;i
class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length();int len;int maxlen=0;int left=0;int right=0;
HashMap map = new HashMap();
while(right=left){
left=map.get(s.charAt(right))+1;
}
}
len=right-left+1;
maxlen=Math.max(maxlen,len);
map.put(s.charAt(right),right);
right=right+1;
}
return maxlen;
}
}
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
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
why there is no code submision
why do we need to do that range checking? I didn't understand
best explanation
Test Case failed on GFG: input = qwertyuioplkjh
output=13, correct output=14.
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;
}
};
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;
}
Superb raj❤
Thanks Brother
can we also do it with set ? instead of hashmap. what issue would it cause
One small addition to the code - the hashmap has to be updated with the location of the right pointer
Thank you very much
Striverrrrrr❤❤❤❤❤🎉🎉
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;
}
Thanks❤
this fails for the case abba, so we can update to l=max(l,v[s[r]]+1)
Thank you so much bro
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;
}
};
Thank you so much
NICE SUPER EXCELLENT MOTIVATED
understood striver.....thanku
Understood❤❤❤
Thanks. Understood.
Can we do this longest substring without repeating characters problem using hashmap in Java?
why last d is not updated
while c is updated
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".
nice video
Understood 😊😊
nice explaination
hy can anyone explain why strivers use hash array instead of the data structure
understood bhaiya
Understood!
s= " " . why doesn't it clear this test case
use vector instead of array
It will be more helpful if u submit in any coding platform
thank you bhaiii
thankyou sir
can we use map here instead of hash array of 255 characters
But space complexity increases 😂
where to find the language specific code
solution in python:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
hashmap={}
left=0
right=0
Max=0
while(right
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
Can we use map here ?
please upload string playlist
Thanku
class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length();int len;int maxlen=0;int left=0;int right=0;
HashMap map = new HashMap();
while(right=left){
left=map.get(s.charAt(right))+1;
}
}
len=right-left+1;
maxlen=Math.max(maxlen,len);
map.put(s.charAt(right),right);
right=right+1;
}
return maxlen;
}
}
understood
Striver❤
Understood.
❤❤❤
Helpfull
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?
great
Understood
left shrinking until valid come
I did using binary search :(
int lengthOfLongestSubstring(string s) {
int n=s.size();
int ans=0;
string a;
for(int i=0;i
10:44
🙌🏻
Understood Sir!
```
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;
}
```
Thank you for your explanation. it was nice.. I solved it.:)
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;
}
Give running code
❤
18/01/25🎉
Fucking Art bro , gg
👍
undersood
Please anyone can help me.. Why we use hash[256] ={0};
initially all possible 256 character's frequency is 0
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