In this guide, you will get 187. Repeated DNA Sequences LeetCode Solution with the best time and space complexity. The solution to Repeated DNA Sequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.
For example, “ACGAATTCCG” is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
Input: s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
Output: [“AAAAACCCCC”,”CCCCCAAAAA”]
Example 2:
Input: s = “AAAAAAAAAAAAA”
Output: [“AAAAAAAAAA”]
Constraints:
1 <= s.length <= 105
s[i] is either 'A', 'C', 'G', or 'T'.
Complexity Analysis
Time Complexity: O(10n) = O(n)
Space Complexity: O(10n) = O(n)
187. Repeated DNA Sequences LeetCode Solution in C++
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_set<string> ans;
unordered_set<string_view> seen;
const string_view sv(s);
for (int i = 0; i + 10 <= s.length(); ++i) {
if (seen.contains(sv.substr(i, 10)))
ans.insert(s.substr(i, 10));
seen.insert(sv.substr(i, 10));
}
return {ans.begin(), ans.end()};
}
}; /* code provided by PROGIEZ */
187. Repeated DNA Sequences LeetCode Solution in Java
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Set<String> ans = new HashSet<>();
Set<String> seen = new HashSet<>();
for (int i = 0; i + 10 <= s.length(); ++i) {
final String seq = s.substring(i, i + 10);
if (seen.contains(seq))
ans.add(seq);
seen.add(seq);
}
return new ArrayList<>(ans);
}
} // code provided by PROGIEZ
187. Repeated DNA Sequences LeetCode Solution in Python
class Solution:
def findRepeatedDnaSequences(self, s: str) -> list[str]:
ans = set()
seen = set()
for i in range(len(s) - 9):
seq = s[i:i + 10]
if seq in seen:
ans.add(seq)
seen.add(seq)
return list(ans) # code by PROGIEZ
