#include #include #include #include using namespace std; int N; string A, B; vector pos[2][4]; map loc = {{'A',0},{'C',1},{'G',2},{'T',3}}; int main() { cin >> N >> A >> B; for (int i=N-1; i >= 0; i--) { pos[0][loc[A[i]]].push_back(i); pos[1][loc[B[i]]].push_back(i); } string result; int a = 0, b = 0; while (true) { for (int j=0; j<4; j++) { while (pos[0][j].back() < a) pos[0][j].pop_back(); while (pos[1][j].back() < b) pos[1][j].pop_back(); } // choose next character wisely... int sumskip = 1000; char choice = '\0'; for (char ch : "ACGT") { if (pos[0][loc[ch]].empty() || pos[1][loc[ch]].empty()) continue; int cost = pos[0][loc[ch]].back() + pos[1][loc[ch]].back() - (a + b); if (cost < sumskip) { sumskip = cost; choice = ch; } } if (choice == '\0') { break; } result += choice; a = pos[0][loc[choice]].back() + 1; b = pos[1][loc[choice]].back() + 1; } cout << result << endl; return 0; }