Repeated DNA Sequences - Leetcode 187 - Python

0:00 - Read the problem
1:10 - Drawing Explanation
5:13 - Coding Explanation

leetcode 187

#meta #facebook #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[greatestever]

Solution :
Every iteration starting from index i = 0 -> size of string - 9
you are getting the substring of 10 characters out from i'th index and adding them to the set, while also checking if the added substring exists in the set.
And if it does, add it to result (which means the 10 character substring appeared more than once).
Then finally returning the result.

I understand this very clearly but wouldn't come up with it on the spot.. I guess more practice in recognizing these patterns will eventually help me get through interviews at tech companies.
Good luck everyone

[mostinho]

Done thanks todo take note
Using hashset to store every 10 letter sequence in the string to check if seen before
If seen before then add it to results hashset so using two hash sets one to identify seen and one to hold the results as a sequence can be found multiple times

[mixtli]

The ratings on these problems is crazy. Some mediums require you to have a PhD in rocket surgery, and some are like this. I think my worry with getting this problem in an interview is I'd be wondering of I'm missing something.. like, some magic solution to get rid of the space for the hash.

[begenchorazgeldiyev]

I think we can use a hashmap instead of a set for seen and the value could be false (meaning we didn’t add to result yet) by default and when seen second time and we add it to our result, we can update it to true.

That way our result can be a list from the start and second check of true or false value would ensure we don’t add it to our result twice.

All said, thank you for a detailed, easy to understand explanation

[poptart-br]

I was kinda worried we might have to use some kinda varriation of KMP to solve this pb until i realized the brute force solution was not so bad + they said 1 <= s.length <= 10e5 :p (+ the video is 8mins long, there is way in hell KMP could fit in 8mins xD)

[masternobody]

me unemployed as always. thanks neetcode

[tusharmishra]

Great videos sir!! your videos are go to whenever I'm stuck on a particular question

[moizurrehman]

time complexity will be O(n*k)
where k = length of string slicing.

to do it in O(n), you have to use rolling hash algorithm.

[admercs]

Here is your 4-bit encoding using a hashmap:

hashmap = {
'A': 0b00,
'T': 0b01,
'C': 0b10,
'G': 0b11
}

print(hashmap['A'])

[anonymy]

I dont understand in example one, why "aaaacccca", not in the output? they also appeared more than once in the string

[sarthakrajput]

Thank you for creating such insightful and helpful videos! Your content is truly valuable, and I really appreciate the effort you put into making these!!

[harigovind]

Isn't substring O(n) operation ? In Java it is. Using rolling hash to compute duplicates is useful here.

[Alchemx]

I'm worried that this initial solution wouldn't satisfy the interviewer. To get full marks I suspect you would have to implement the space saving mapping technique you review, or the bitmasking solution provided as solution #3 on leetcode.

[anonymoussloth]

Instead of two hash sets, couldn't we use a hash map to store the frequency of each string? And for all the strings with frequency more than or equal to two, ad those to the list.

[mucle]

hash sets hash the input. I don't think it saves space. Similar to websites that limit how long your password can be. No website saves your password, they save a >100 character long hash of your password

[axeliuxTEC]

What is the time complexity for cur = s[ l: l + 9] ? Isn't that O(k) where k is the size of the substring? Then wouldn't the time complexity of this solution is O (n * k ) where n is the size of the dns sequence and k the size of the substrings?

Why are we taking on this video that the complexity of this is O (n ) ?

In java though, this would be O ( n ) given how Java handles substring though ;)

[jordangamble]

Superb content. Was wondering if you could go over 1155. Number of Dice Rolls With Target Sum on LeetCode. Got asked this problem in a mock interview with a Google Engineer

[yashshukla]

got asked this in the interview and failed the interview. should have watched this vid. so so sad. :(((

[shauryakumar]

why this is not working:
vector<string> s) {
int n = s.size();
vector<string> ans;
if(n < 10) return ans;
map<string, int> m;
int i=0;
int j=0;

string temp = "";
while(j < n){
temp += s[j];
if(j-i+1 < 10) j++;

else if(j-i+1 == 10){
m[temp]++;
//so that it will be included only once if more than one occurence
if(m[temp] == 2) ans.push_back(temp);
j++;
}

else{
temp.erase(0, 1);
i++;
j++;
}
}
return ans;
}

[anandakrishnanp]

10 letter long Substrings like


are also repeated . The solution provided does cover these as well, just that the example hasn't provided all