// SUBTASK ???
#include <bits/stdc++.h>
#include "dna.h"
//#include "grader.cpp"
using namespace std;
string a, b;
vector <int> pref;
vector <vector<int>> pref_a;
vector <vector<int>> pref_b;
vector <vector<int>> cnt(3, vector<int>(3));
int id(char ch)
{
if (ch == 'A') return 0;
if (ch == 'T') return 1;
return 2;
}
void init(string A, string B)
{
a = A;
b = B;
int n = a.size();
pref.resize(n);
pref_a.resize(3, vector<int>(n));
pref_b.resize(3, vector<int>(n));
for (int i = 0; i < n; i++)
{
if (a[i] == 'A')
{
pref_a[0][i] = i > 0 ? pref_a[0][i - 1] + 1 : 1;
}
else pref_a[0][i] = i > 0 ? pref_a[0][i - 1] : 0;
if (a[i] == 'T')
{
pref_a[1][i] = i > 0 ? pref_a[1][i - 1] + 1 : 1;
}
else pref_a[1][i] = i > 0 ? pref_a[1][i - 1] : 0;
if (a[i] == 'C')
{
pref_a[2][i] = i > 0 ? pref_a[2][i - 1] + 1 : 1;
}
else pref_a[2][i] = i > 0 ? pref_a[2][i - 1] : 0;
if (b[i] == 'A')
{
pref_b[0][i] = i > 0 ? pref_b[0][i - 1] + 1 : 1;
}
else pref_b[0][i] = i > 0 ? pref_b[0][i - 1] : 0;
if (b[i] == 'T')
{
pref_b[1][i] = i > 0 ? pref_b[1][i - 1] + 1 : 1;
}
else pref_b[1][i] = i > 0 ? pref_b[1][i - 1] : 0;
if (b[i] == 'C')
{
pref_b[2][i] = i > 0 ? pref_b[2][i - 1] + 1 : 1;
}
else pref_b[2][i] = i > 0 ? pref_b[2][i - 1] : 0;
if (a[i] != b[i])
{
pref[i] = i > 0 ? pref[i - 1] + 1 : 1;
}
else pref[i] = i > 0 ? pref[i - 1] : 0;
}
}
bool validate(int x, int y)
{
int br_aA = x > 0 ? pref_a[0][y] - pref_a[0][x - 1] : pref_a[0][y];
int br_aT = x > 0 ? pref_a[1][y] - pref_a[1][x - 1] : pref_a[1][y];
int br_aC = x > 0 ? pref_a[2][y] - pref_a[2][x - 1] : pref_a[2][y];
int br_bA = x > 0 ? pref_b[0][y] - pref_b[0][x - 1] : pref_b[0][y];
int br_bT = x > 0 ? pref_b[1][y] - pref_b[1][x - 1] : pref_b[1][y];
int br_bC = x > 0 ? pref_b[2][y] - pref_b[2][x - 1] : pref_b[2][y];
return (br_aA == br_bA && br_aT == br_bT && br_aC == br_bC);
}
int get_distance(int x, int y)
{
if (!validate(x, y)) return -1;
cnt.assign(3, vector<int>(3));
for (int i = x; i <= y; i++)
{
if (a[i] == b[i]) continue;
int id1 = id(a[i]), id2 = id(b[i]);
cnt[id1][id2]++;
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
//cout << cnt[i][j] << " ";
}
//cout << endl;
}
int ans = 0, remain = 0;
int swaps1 = min(cnt[0][1], cnt[1][0]);
remain += max(cnt[0][1], cnt[1][0]) - swaps1;
ans += swaps1;
int swaps2 = min(cnt[0][2], cnt[2][0]);
remain += max(cnt[0][2], cnt[2][0]) - swaps2;
ans += swaps2;
int swaps3 = min(cnt[1][2], cnt[2][1]);
remain += max(cnt[1][2], cnt[2][1]) - swaps3;
ans += swaps3;
ans += (remain / 3) * 2;
return ans;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
2
1
-1
2 1
AA
TT
0 1
*/
