<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 {
public:
    // int findCount(const string& s, int low, int high, string& curr){
    //     int ans = 0;
    //     for(int i = low; i <= high; i++){
    //         int j = 0;
    //         int start = i;
    //         while(j < curr.size() && start <= high && s[start] == curr[j]){
    //             j++;
    //             start++;
    //         }
    //         if(j == curr.size()) ans++;
    //     }
    //     return ans;
    // }
    // vector<string> findRepeatedDnaSequences(string s) {
    //     vector <string> ans;
    //     int n = s.size();
    //     if(n < 10) return ans;
    //     string curr = s.substr(0, 10);
    //     set <string> covered;
    //     int count = findCount(s, 0, n-1, curr);
    //     if(count >= 2) ans.push_back(curr);
    //     covered.insert(curr);
    //     for(int i = 10; i <= n-1; i++){
    //         curr = curr.substr(1) + s[i];
    //         if(covered.find(curr) == covered.end()){
    //             covered.insert(curr);
    //             if(findCount(s, i-9, n-1, curr) >= 2) ans.push_back(curr);
    //         }
    //     }
    //     return ans;
    // }

    vector<string> findRepeatedDnaSequences(string s){
        unordered_map <long long int, int> count;
        vector <string> ans;
        int n = s.size();
        if(n < 10) return ans;
        string curr;
        map <char, char> mp;
        mp['A'] = '0';
        mp['C'] = '1';
        mp['G'] = '2';
        mp['T'] = '3';
        for(int i = 0; i < 10; i++) curr += mp[s[i]];
        count[stoll(curr)]++;
        for(int i = 10; i < s.size(); i++){
            curr = curr.substr(1);
            curr += mp[s[i]];
            count[stoll(curr)]++;
        }
        map <char, int> rev_mp;
        rev_mp[0] = 'A';
        rev_mp[1] = 'C';
        rev_mp[2] = 'G';
        rev_mp[3] = 'T';
        for(auto &[num, freq]: count){
            cout << num << " ";
            if(freq >= 2){
                string curr = to_string(num);
                string s;
                for(int i = 0; i < 10 - curr.size(); i++) s += "A";
                for(auto ele: curr){
                    string num;
                    num += ele;
                    s += rev_mp[stoi(num)];
                }
                ans.push_back(s);
            }
        }
        cout << "\n";
        return ans;
    }
};

20146