/* Ignut
started: 17.08.2024
now: 17.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string a, b;
void init(string A, string B) {
a = A, b = B;
}
vector<char> vec = {'A', 'C', 'T'};
int get_distance(int x, int y) {
int cntAx = 0, cntCx = 0;
int cntAy = 0, cntCy = 0;
map<pair<char, char>, int> cnt;
for (int i = x; i <= y; i ++) {
if (a[i] == 'A') cntAx ++;
else if (a[i] == 'C') cntCx ++;
if (b[i] == 'A') cntAy ++;
else if (b[i] == 'C') cntCy ++;
cnt[{a[i], b[i]}] ++;
}
if (cntAx != cntAy || cntCx != cntCy) return -1;
// int total = 0, mn = y - x + 1;
// for (int i = 0; i < 3; i ++) {
// for (int j = 0; j < 3; j ++) {
// if (i == j) continue;
// total += cnt[{vec[i], vec[j]}];
// mn = min(mn, cnt[{vec[i], vec[j]}]);
// }
// }
int total = 0, mn = y - x + 1;
mn = min({abs(cnt[{'A', 'T'}] - cnt[{'T', 'A'}]), abs(cnt[{'A', 'C'}] - cnt[{'C', 'A'}]), abs(cnt[{'C', 'T'}] - cnt[{'T', 'C'}])});
for (int i = x; i <= y; i ++) total += (a[i] != b[i]);
return (total - mn) / 2 + mn;
}
