10252 Common Permutation

題目連結

題目翻譯

給定兩個全為小寫字母的字串 a 和 b，請找出最長的字串 x，使得 x 的某個排列是 a 的子序列，且 x 的另一個排列是 b 的子序列。

輸入

輸入包含多組測資，每兩行為一組：第一行是字串 a，第二行是字串 b，每個字串長度最多 1000 個小寫字母。

輸出

每組測資輸出一行 x；若有多組答案長度相同，輸出其中字母順序（alphabetical order）最小的那一個。

解題思路

題目只要求「x 的某個排列」是子序列，並未要求字母的相對順序，所以本質上就是比較兩字串中每個字母各自出現的次數，取兩邊次數的較小值；接著依照 a 到 z 的順序，把每個字母重複輸出對應的次數，就是長度最大、且字典序最小的答案。

程式碼

#include <bits/stdc++.h>
using namespace std;
//author:Jackis666
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    string s,t;
    while(getline(cin,s)){
        getline(cin,t);
        vector<int> a(26,0),b(26,0);
        for(auto c:s) if(c>='a') a[c-'a']++;else a[c-'A']++;
        for(auto c:t) if(c>='a') b[c-'a']++;else b[c-'A']++;
        for(int i=0;i<26;i++){
            for(int k=0;k<min(a[i],b[i]);k++){
                cout<<(char)('a'+i);
            }
        }
        cout<<"\n";
    }
}