<p>The <strong>DNA sequence</strong> is composed of a series of nucleotides abbreviated as <code>&#39;A&#39;</code>, <code>&#39;C&#39;</code>, <code>&#39;G&#39;</code>, and <code>&#39;T&#39;</code>.</p>

<ul>
	<li>For example, <code>&quot;ACGAATTCCG&quot;</code> is a <strong>DNA sequence</strong>.</li>
</ul>

<p>When studying <strong>DNA</strong>, it is useful to identify repeated sequences within the DNA.</p>

<p>Given a string <code>s</code> that represents a <strong>DNA sequence</strong>, return all the <strong><code>10</code>-letter-long</strong> sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
<strong>Output:</strong> ["AAAAACCCCC","CCCCCAAAAA"]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "AAAAAAAAAAAAA"
<strong>Output:</strong> ["AAAAAAAAAA"]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;A&#39;</code>, <code>&#39;C&#39;</code>, <code>&#39;G&#39;</code>, or <code>&#39;T&#39;</code>.</li>
</ul>

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        if len(s) < 10:
            return []

        res = set()
        uniques = set()
        s_list = list(s)

        l = 0
        for r in range(len(s_list)):
            if r >= 9:
                substr = "".join(s_list[l: r + 1])
                if substr in uniques:
                    res.add(substr)
                uniques.add(substr)
                l += 1
            
        return list(res)

'''
Understanding:
Rephrase: Find repeating substrings of length 10.

Questions:
-> What are the parameters of the string's length? Can it be empty or < 10?
    -> Not empty. [1, 10^5]
-> What characters can the string hold? 
    -> 'A', 'C', 'G', 'T'
-> Are there complexity constraints?
    -> Unsure. O(N) Time, O(N) space

Edge Case: Strings of length 1-9. Don't meet parameters

Match: 
Set() for unique strings of length 10
Sliding Window 
Return array
Convert array to list

Plan:
# Edge Case:
if len(s) < 10:
    return []

res = []
uniques = set()
s_list = list(s)

l = 0
for r in range(len(s_list)):
    if r >= 9:
        substr = s_list[l: r + 1]
        if substr in uniques:
            res.append(str(substr))
        uniques.add(substr)
        l += 1
    
return res
'''
29300