<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>


import collections

# https://www.math.utah.edu/~pa/MDS/primes.html
PRIME_NUM = 997  #2147483647 #997

class Solution:

    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        size = len(s)
        if size < 11:
            return []
        # b0, b1, b10, b11 
        d = {
            'A': 1,
            'C': 2,
            'G': 3,
            'T': 4
        }
        # MULTI = 4
        # ACG = 1*10^2 + 2*10 + 3 = 123
        num = 0
        for i in range(10):  # first 10 letters
            c = s[i]
            num = num*10 + d[c]
        sign = num % PRIME_NUM
        high = 10**9
        sign_d = collections.defaultdict(list)
        # print(sign)
        # sign_list = [0 for _ in range(size-10)]
        sign_d[sign] = [0]
        for i in range(10, size):
            c = s[i]
            num = (num - high*d[s[i-10]])*10 + d[c]
            sign = num % PRIME_NUM
            sign_d[sign].append(i-9)
        
        # print(sign_d)

        res = set()
        for idx_list in sign_d.values():
            if len(idx_list) == 1:
                continue
            count = collections.Counter()
            for i in idx_list:
                word = s[i:i+10]
                count[word] += 1
            for word, c in count.items():
                if c > 1:
                    res.add(word)
        return list(res)
        # return []

20800