#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using paira = array<int, 2>;
int n = 1;
vector<int> same(1);
vector<vector<int>> counta(3, vector<int>(1));
vector<vector<vector<int>>> ma(3, vector<vector<int>>(3, vector<int>(n)));
auto countb = counta;
void init(string a, string b) {
n = a.size();
same.resize(n+1);
for (int i = 0; i < 3; i++) {
counta[i].resize(n+1);
countb[i].resize(n+1);
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
ma[i][j].resize(n+1);
}
}
for (int i = 0; i < n; i++) {
int ai = (a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2));
int bi = (b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2));
for (int j = 0; j < 3; j++) {
counta[j][i + 1] = counta[j][i];
countb[j][ i + 1] = countb[j][i];
}
counta[ai][i+1]++;
counta[bi][i+1]++;
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
ma[j][k][i+1] = ma[j][k][i];
}
}
ma[ai][bi][i+1]++;
same[i + 1] = (i == 0 ? 0 : same[i]) + (ai == bi);
}
}
int get_distance(int x, int y) {
for (int i = 0; i < 3 ; i++) {
if (counta[i][y+1] - counta[i][x] != countb[i][y+1] - countb[i][x]) {
return -1;
}
}
int ans = 0;
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < 3; j++) {
ans += min(ma[i][j][y + 1] - ma[i][j][x], ma[j][i][y + 1] - ma[j][i][x]);
}
};
int a = (ma[0][1][y + 1] - ma[0][1][x]), b= ( ma[1][0][y + 1] - ma[1][0][x]);
ans += 2*(max(a, b) - min(a ,b));
return ans;
}
/*
constraints n = 1e5
q = 1e5
at most 3 different
q*log(n) or q solution allowed
same[n] = number of "matching" indices for x and y until n
then
If two strings who are derranged permutations of each other then their edit distance is
for even n n/2
for odd n (n-1)/2 + 1 = (n-1+2)/2 = (n+1)/2
*/
