#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int pre[100'050][3][3];
void init(std::string a, std::string b) {
assert(a.length() == b.length());
const int n = a.length();
auto id = [](char c) -> int {
return (c == 'A' ? 0 : (c == 'C' ? 1 : 2));
};
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
pre[i][j][k] += pre[i - 1][j][k];
}
}
pre[i][id(a[i - 1])][id(b[i - 1])]++;
}
}
int get_distance(int x, int y) {
int arr[3][3], diff[3];
fill(diff, diff + 3, 0);
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
arr[j][k] = pre[y + 1][j][k] - pre[x][j][k];
diff[j] += arr[j][k];
diff[k] -= arr[j][k];
}
}
for (int i = 0; i < 3; i++) {
if (diff[i] != 0) {
return -1;
}
}
int res = 0;
// Swap pairs first
for (int j = 0; j < 3; j++) {
for (int k = 0; k < j; k++) {
int pair_swaps = min(arr[j][k], arr[k][j]);
arr[j][k] -= pair_swaps;
arr[k][j] -= pair_swaps;
res += pair_swaps;
}
}
// I believe over here there are left with only triplets
// Furthermore the frequency that A, C, T appears should be equal
int triplet_swaps = max(arr[0][1], arr[1][0]);
assert(triplet_swaps == max(arr[0][2], arr[2][0]) && triplet_swaps == max(arr[1][2], arr[2][1]));
res += 2 * triplet_swaps;
return res;
}
