#include "bits/stdc++.h"
#include "dna.h"
using namespace std;
vector<string> swap(string a, string par){
vector<string> swaps;
for(int i=0;i<a.size()-1;i++){
for(int j=i+1;j<a.size();j++){
string ye = "";
ye = a;
char save = a[i];
ye[i] = a[j];
ye[j] = save;
if(ye==par) continue;
swaps.push_back(ye);
}
}
return swaps;
}
int bigger_count = 0;
bool dfs(int ind, std::string a, std::string b, string par, vector<vector<string>> &tree, int &count)
{
if (a==b){
count++;
if(count < bigger_count || bigger_count==0) bigger_count = count;
return true;
}
if (count > bigger_count && bigger_count != 0) return false;
tree[ind] = swap(a, par);
for(int i=0;i<tree[ind].size();i++){
if(tree[ind][i] == par) continue;
count++;
if(dfs(ind+1,tree[ind][i],b,a,tree,count)){
if(count < bigger_count || bigger_count==0) bigger_count = count;
return true;
}
}
return false;
}
bool count(string a, string b){
int countaA=0, countaT=0, countaC=0;
int countbA=0, countbT=0, countbC=0;
for(int i=0;i<a.size();i++){
if(a[i]=='A') countaA++;
else if(a[i]=='T') countaT++;
else if(a[i]=='C') countaC++;
if(b[i]=='A') countbA++;
else if(b[i]=='T') countbT++;
else if(b[i]=='C') countbC++;
}
if(countaA==countbA && countaT==countbT && countaC==countbC){
return true;
} else{
return false;
}
}
string f="", s="";
void init(std::string a, std::string b) {
f=a;
s=b;
}
int get_distance(int x, int y) {
vector<vector<string>> tree(pow(f.size(), s.size()));
int counter = 0;
string ns;
string fs;
for(int i=x-1;i<y;i++){
ns += f[i];
fs += s[i];
}
if(ns==fs) return 0;
if(!count(f,s)) return -1;
tree[0] = {ns};
if(dfs(1,ns,fs,"",tree,counter)){
return bigger_count-1;
}
return -1;
}
