题解 | #DNA序列# 集合，穷举，数学

使用集合存储当前的种类，同时举例子可知长度为 i 的一共有 4^i 种

#include <iostream>
#include <cmath>
#include <unordered_set>
using namespace std;

int main() {
    string str;
    while (cin >> str) {
        int length = str.length();
        unordered_set<string> st;
        string substring;
        for (int i = 1; i <= length; i++) {
            // 清空集合，仅计算当前长度的种类数
            st.clear();
            // 遍历并截取对应长度的字符，插入集合中
            for (int j = 0; j < length - i + 1; j++) {
                substring = str.substr(j, i);
                st.insert(substring);
            }
            // 长度为 i 的种类总数是 4^i
            if (st.size() != pow(4, i)) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

时间复杂度：

1、最外层while循环会根据输入的字符串进行迭代，时间复杂度取决于输入字符串的长度，设为n

2、外层遍历所有可能的子字符串长度，时间复杂度为O(n)；内层遍历字符串的所有可能起始位置，时间复杂度为O(n)

综上所述，总时间复杂度为O(n^2)

空间复杂度：

1、字符串变量str的空间复杂度为O(n)

2、无序集合st的空间复杂度取决于子字符串的数量，最坏情况下为O(n^2)

综上所述，总空间复杂度为O(n^2)