题意

给只包含ATGC的字符串，求其中长度恰好为10且出现过大于1次的字符串

限制：

字符串总长度不大于$10^{5}10^5$

方法

unordered_map+string

建立两个辅助unordered_map和一个排序数组

1. 记录每个长度为10的字符串出现的次数
2. 记录每个长度为10的字符串上次出现的位置
3. 记录所有大于一次出现的pair<首次出现位置，字符串>

这样利用stl的性质，可以知道是否出现次数大于1次

最后对数组进行排序输出即可。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串vector
     */
    vector<string> repeatedDNA(string DNA) {
        unordered_map<string,int> s2i; // 出现次数
        unordered_map<string,int> s2p; // 首次出现位置
        string s = "";
        for(int i = 0;i<10;i++){ // 初始化前10个
            s+=DNA[i];
        }
        s2i[s] ++;
        s2p[s] = 9;
        vector<pair<int,string> > ans ; // 位置，字符串
        for(int i =10;i<DNA.size();i++){
            s+=DNA[i];
            s=s.substr(1);
            if(s2i[s] == 1){ // 出现超过一次
                ans.push_back({s2p[s],s}); // 加入到数组中
            }
            s2i[s]++; // 计数+1
            s2p[s] = i;
        }
        sort(ans.begin(),ans.end()); // 按照首次出现位置排序
        vector<string> r;
        for(auto item:ans){ // 输出
            r.push_back(item.second);
        }
        return r;
    }
};

复杂度分析

设限制的长度为 $m=10m=10$

时间复杂度: 对于每个长度为10的字符串，获得的时间复杂度$O(1)O(1)$，在unordered_map中查询的复杂度为$O(1)O(1)$, 最后输出最坏情况出现大量出现两次的字符串，所以总时间复杂度为$O(nm)O(nm\; )$

空间复杂度: 最坏情况是所有字符串都不相同，所以空间复杂度为$O(max(n,4^m))O(max(n,4^m))$

基于数值映射的时间效率优化

上面利用了unordered_map和stl的string，注意到出现的字母只有4种，而长度限制是恰好为10，注意到$4^{1}0=10485764^10=1048576$

考虑直接对字符串和数值做映射和反映射操作，把ATGC和0123一一映射，这样查询就直接是数组下标，而不需要走unordered_map

以题目的样例数据AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT 为例

最后对(首次出现位置，值)数组： [{0,1023},{5,1047552}] 进行排序

最后再把数值反向还原为字符串输出即可。

代码

class Solution {
public:
    char int2ch(int v){ // 编码到字符
        if(v == 0)return 'A';
        if(v == 1)return 'T';
        if(v == 2)return 'G';
        if(v == 3)return 'C';
        assert(false);
        return -1;
    }
    int ch2int(char ch){ // 字符到编码
        if(ch == 'A')return 0;
        if(ch == 'T')return 1;
        if(ch == 'G')return 2;
        if(ch == 'C')return 3;
        assert(false);
        return -1;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串vector
     */
    vector<string> repeatedDNA(string DNA) {
        // write code here
        vector<int> s2i((1<<20)+1,0); // 出现次数
        vector<int> s2p((1<<20)+1,0); // 出现次数
        int v = 0;
        for(int i = 0;i<10;i++){ // 初始化前10个
            v*=4;
            v+=ch2int(DNA[i]);
        }
        s2i[v] ++;
        s2p[v] = 9;
        vector<pair<int,int> > ans ; // 位置，字符串编码
        for(int i =10;i<DNA.size();i++){
            v*=4;
            v+=ch2int(DNA[i]);
            v%=(1<<20);
            if(s2i[v] == 1){ // 出现超过一次
                ans.push_back({s2p[v],v});
            }
            s2i[v]++; // 计数+1
            s2p[v] = i;
        }
        sort(ans.begin(),ans.end()); // 按照首次出现位置排序
        vector<string> r; // 结果数组
        for(auto item:ans){
            int v = item.second;
            string s = "";
            for(int i=0;i<10;i++){ // 转码回字符串
                s=int2ch(v%4)+s;
                v/=4;
            }
            r.push_back(s);
        }
        return r;
    }
};

复杂度分析

时间复杂度: 对于每个长度为10的字符串，获得的时间复杂度$O(1)O(1)$，在数组中查询的复杂度为$O(1)O(1)$, 最后输出最坏情况出现大量出现两次的字符串，所以总时间复杂度为$O(nm)O(nm)$

空间复杂度: 最坏情况是所有字符串都不相同，所以空间复杂度为$O(max(n,4^m))O(max(n,4^m))$