L3. Longest Substring Without Repeating Characters | 2 Pointers and Sliding Window Playlist
HTML-код
- Опубликовано: 25 мар 2024
- Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.org/strivers-a2z...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/takeuforward
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!
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.
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;
}
I solved it on my own! Your teaching is amazing bhaiya!!!
You are unstoppable... 🙏🙏 You are the best 🙏🙏
Need such type of teachers
I think you haven't attached this youtube link in your take youforward site.
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;
}
Great bhaiji 🙏
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
East and west striver bhaiya is best ❤❤
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++;
Thank you very much
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?
hi Striver,
Your Graph, DP, binary search playlist are amazing. Please create a playlist for String as well.
Thanks. Understood.
Thank you so much bro
best explanation
Thanks Brother
understood striver.....thanku
NICE SUPER EXCELLENT MOTIVATED
Thanks❤
solution in python:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
hashmap={}
left=0
right=0
Max=0
while(right
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
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
Thanku
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
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;
}
};
great
Understood!
public static void main( String[] args )
{
String s ="pwwkew";
String count ="";
int max =0;
int count1=0;
for(int i=0;i
Striver❤❤❤
Striverrrrrr❤❤❤❤❤🎉🎉
Striver❤
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
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
why there is no code submision
❤❤❤
It will be more helpful if u submit in any coding platform
please upload string playlist
🙌🏻
❤❤
why do we need to do that range checking? I didn't understand
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
hy can anyone explain why strivers use hash array instead of the data structure
where to find the language specific code
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".
s= " " . why doesn't it clear this test case
👍
undersood
god
10:44
Test Case failed on GFG: input = qwertyuioplkjh
output=13, correct output=14.
Anybody please give that code for java
Give running code
us
int lengthOfLongestSubstring(string s) {
int n=s.size();
int ans=0;
string a;
for(int i=0;i
```
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;
}
```
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?
too long video
Beginners like me need such explanation. You also would have started from zero only
Please anyone can help me.. Why we use hash[256] ={0};
initially all possible 256 character's frequency is 0
worst acche se code de doge to kya jayega bakwas explanation
You are awesome Striver,
[Comment down guys, how many leetcode question y'all have solved so far, and in which semester you are currently in ?]
Solved 350+ Qs on Coding Ninjas, started Leetcode this month. I am in 2nd sem of NIT-A CSE
@@SOUVIK-po9jtbkl pagal hai kya
@@SOUVIK-po9jt tf
@@Cubeone11 we actually have to compete with these type of guys lol. IITians start cp in 1st sem ive heard, imagine offcampus you sit for the same job interview
@@user-fw4kz3bb4g U r correct. I have many batchmates not only in CSE but also other branches who are well-versed in CP and won CP competitions organised by our college
❤❤❤