题解 | DNA序列

#include <iostream>
using namespace std;

int main() {
    string gene;
    int length;
    cin >> gene >> length;
    int count_CG = 0;
    int start = 0, end = length - 1;
    for(int i = start; i <= end; ++i) {
        if(gene[i] == 'C' || gene[i] == 'G') {
            ++count_CG;
        }
    }
    int max_idx = start;
    int max_CG = count_CG;
    while(++end < gene.size()) {
        if(gene[start] == 'C' || gene[start] == 'G') {
            --count_CG;
        }
        if(gene[end] == 'C' || gene[end] == 'G') {
            ++count_CG;
        }
        ++start;
        if(max_CG < count_CG) {
            max_CG = count_CG;
            max_idx = start;
        }
    }       
    cout << gene.substr(max_idx, length) << endl;
    return 0;
}

滑动窗口，时间复杂度为O(n)