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

from collections import defaultdict

class Solution:
    # using rolling hash approach of Rabin Karp Algo
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        mappings = {
            'A': 1, 'C': 2, 'G': 3, 'T': 4
        }

        n = len(s)
        m = 9
        if n <= m:
            return []
        
        tHash = 0
        seen = defaultdict(int)
        for i in range(0, m+1):
            tHash = tHash * 4 + mappings[s[i]]
        seen[tHash] = 1

        result = []
        for i in range(1, n - m):
            # - remove the leftmost character from the hash value
            # - shift remaining hash value left by 1 (multiply by 4 as we using base 4)
            # - add the new rightmost character
            # 
            # using 4^9 because we have 10 characters, and the leftmost is at
            # the 10th position (count from 0)
            tHash = (tHash - (4 ** m) * mappings[s[i-1]]) * 4 + mappings[s[i + m]]
            # print(tHash, s[i:i + m + 1])

            seen[tHash] += 1
            if seen[tHash] == 2:
                # print(tHash, s[i:i + m + 1])
                result.append(s[i:i + m + 1])

        return result

27400