#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n;
string s, t;
vector<vector<int>> pref1, pref2, inds;
vector<string> pr;
map<string, vector<vector<int>>> mp;
void init(std::string a, std::string b) {
s = a;
t = b;
n = (int) s.length();
pref1 = vector<vector<int>>(n, vector<int>(26));
pref2 = vector<vector<int>>(n, vector<int>(26));
pref1[0][s[0] - 'A']++;
pref2[0][t[0] - 'A']++;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++) {
pref1[i][j] = pref1[i - 1][j];
pref2[i][j] = pref2[i - 1][j];
}
pref1[i][s[i] - 'A']++;
pref2[i][t[i] - 'A']++;
}
auto getPrefix = [&](char c, char d) {
vector<int> pref(n);
if (s[0] == c && t[0] == d) {
pref[0] = 1;
}
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1];
if (s[i] == c && t[i] == d) {
pref[i]++;
}
}
return pref;
};
string str = "ACT";
int m = (int) str.length();
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
string cur;
cur += str[i];
cur += str[j];
vector<int> pref1 = getPrefix(str[i], str[j]);
vector<int> pref2 = getPrefix(str[j], str[i]);
mp[cur].push_back(pref1);
mp[cur].push_back(pref2);
}
}
inds.resize(26);
for (int i = 0; i < n; i++) {
if (s[i] == t[i]) {
inds[s[i] - 'A'].push_back(i);
}
}
}
int get_distance(int x, int y) {
for (int j = 0; j < 26; j++) {
int cnt1 = pref1[y][j] - (x > 0 ? pref1[x - 1][j] : 0);
int cnt2 = pref2[y][j] - (x > 0 ? pref2[x - 1][j] : 0);
if (cnt1 != cnt2) {
return -1;
}
}
int cntA = pref1[y][0] - (x > 0 ? pref1[x - 1][0] : 0);
int len = y - x + 1;
for (int i = 0; i < 26; i++) {
if (inds[i].empty()) {
continue;
}
auto ub = upper_bound(inds[i].begin(), inds[i].end(), y);
auto lb = lower_bound(inds[i].begin(), inds[i].end(), x);
if (ub == inds[i].begin()) {
continue;
}
if (lb == inds[i].end()) {
continue;
}
--ub;
int aa = ub - inds[i].begin();
int bb = lb - inds[i].begin();
swap(aa, bb);
len -= (bb - aa + 1);
if (i == 0) {
cntA -= (bb - aa + 1);
}
}
int res = 0;
for (auto& [str, pref] : mp) {
int cnt1 = pref[0][y] - (x > 0 ? pref[0][x - 1] : 0);
int cnt2 = pref[1][y] - (x > 0 ? pref[1][x - 1] : 0);
int rem = min(cnt1, cnt2);
if (str[0] == 'A') {
cntA -= rem;
}
len -= 2 * rem;
res += rem;
}
res += cntA;
len -= cntA;
return res + len / 2;
}
