【題解】CSES 1087 Shortest Subsequence

【題目敘述】https://cses.fi/problemset/task/1087/
【解題想法】貪心

#include <iostream>
#include <set>
using namespace std;
string s, ans = "";
set<char> st;

int main() {
    cin >> s;
    for (int i = 0; i < (int)s.size(); i++) {
        //找出含有四個字母的最短子字串,紀錄最後一個出現的字母
        //例子:ACGT ACGT -> TT
        st.insert(s[i]);
        if ((int)st.size() == 4){
            ans += s[i];
            st.clear();
        }
    }
    for (char i: "ACGT") {
        //餘下的集合中,未曾出現過的字母
        //從中擇一,即可構造出答案
        if (!st.count(i)) {
            ans += i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}
分享本文 Share with friends