#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> pref, pref2;
map<char, int> mp;
int n;
vector<vector<vector<int>>> cnt;
void init(std::string _a, std::string _b) {
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
n = (int)_a.size();
vector<int> a(n), b(n);
for(int i = 0; i < n; ++i) {
a[i] = mp[_a[i]];
}
for(int i = 0; i < n; ++i) {
b[i] = mp[_b[i]];
}
pref.assign(n, vector<int>(3, 0));
pref2.assign(n, vector<int>(3, 0));
pref[0][a[0]] = 1;
for(int i = 1; i < n; ++i) {
for(int j = 0; j < 3; ++j) {
pref[i][j] = pref[i-1][j];
}
++pref[i][a[i]];
}
pref2[0][b[0]] = 1;
for(int i = 1; i < n; ++i) {
for(int j = 0; j < 3; ++j) {
pref2[i][j] = pref2[i-1][j];
}
++pref2[i][b[i]];
}
cnt.assign(n, vector<vector<int>>(3, vector<int>(3, 0)));
cnt[0][a[0]][b[0]] = 1;
for(int i = 1; i < n; ++i) {
for(int j = 0; j < 3; ++j) {
for(int k = 0; k < 3; ++k) {
cnt[i][j][k] = cnt[i-1][j][k];
}
}
++cnt[i][a[i]][b[i]];
}
}
int get_distance(int x, int y) {
for(int j = 0; j < 3; ++j) {
int s1 = pref[y][j];
if(x-1 >= 0)
s1 -= pref[x-1][j];
int s2 = pref2[y][j];
if(x-1 >= 0)
s2 -= pref2[x-1][j];
if(s1 != s2) {
return -1;
}
}
int ans = 0;
int vel = y - x + 1;
for(int j = 0; j < 3; ++j) {
int s1 = cnt[y][j][j];
if(x-1 >= 0)
s1 -= cnt[x-1][j][j];
vel -= s1;
}
for(int j = 0; j < 3; ++j) {
for(int k = j+1; k < 3; ++k) {
int ima1 = cnt[y][j][k];
if(x - 1 >= 0)
ima1 -= cnt[x-1][j][k];
int ima2 = cnt[y][k][j];
if(x - 1 >= 0)
ima2 -= cnt[x-1][k][j];
ans += min(ima1, ima2);
vel -= 2*min(ima1, ima2);
}
}
//konacno ce izgledati oblika
//CCAATT
//TTCCAA
//ovde treba 4 poteza
ans += (vel / 3) * 2;
return ans;
}
