Repeated DNA Sequences — LeetCode 187 Python Solution
MediumBit ManipulationHash TableStringSliding WindowHash FunctionRolling Hash
- Problem
- #187
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'. For example, "ACGAATTCCG" is a DNA sequence.
Example
- Input
- s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
- Output
- ["AAAAACCCCC","CCCCCAAAAA"]
Python solution
Python
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
cnt = Counter()
ans = []
for i in range(len(s) - 10 + 1):
t = s[i : i + 10]
cnt[t] += 1
if cnt[t] == 2:
ans.append(t)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times 10) |
| Space | O(n \times 10) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 187. Repeated DNA Sequences is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
LeetCode 1461Check If a String Contains All Binary Codes of Size KMediumLeetCode 1016Binary String With Substrings Representing 1 To NMediumLeetCode 1763Longest Nice SubstringEasyLeetCode 3Longest Substring Without Repeating CharactersMediumLeetCode 30Substring with Concatenation of All WordsHardLeetCode 76Minimum Window SubstringHard
Frequently asked questions
- How hard is LeetCode 187. Repeated DNA Sequences?
- LeetCode 187. Repeated DNA Sequences is rated Medium on LeetCode.
- What is the time complexity of LeetCode 187. Repeated DNA Sequences?
- The Python solution on this page runs in O(n \times 10).
- What is the space complexity of LeetCode 187. Repeated DNA Sequences?
- The Python solution on this page uses O(n \times 10) auxiliary space.
- What topics does LeetCode 187. Repeated DNA Sequences cover?
- LeetCode 187. Repeated DNA Sequences is tagged Bit Manipulation, Hash Table, String, Sliding Window, Hash Function and Rolling Hash on LeetCode.