/* Solution to Game Night by Mees * * Brute force solution in square time. * * Expected answer: TIME LIMIT EXCEEDED. * */ #include #include #include #include using namespace std; template class circ_array { vector v; int n; public: circ_array(size_t size) { n = size; v = vector(n); } T& operator[](int idx) { return v[((idx%n)+n)%n]; } const T& operator[](const int idx) const { return v[((idx%n)+n)%n]; } void reverse() { std::reverse(v.begin(), v.end()); } }; int main() { int n; cin >> n; circ_array table = circ_array(n); string s; cin >> s; vector ct(3, 0); for(int i = 0; i < n; i++) { table[i] = s[i]; ct[s[i] - 'A']++; } int cur_best = n + 1; for(int dummy = 0; dummy < 2; dummy++) { vector> mismatch(3, vector(3, 0)); for(int j = 0; j < n; j++) { int movers = 0; for(int k = 0; k < ct[0]; k++) { if(table[j+k] != 'A') movers++; } for(int k = ct[0]; k < ct[0] + ct[1]; k++) { if(table[j+k] != 'B') movers++; } for(int k = ct[0] + ct[1]; k < n; k++) { if(table[j+k] != 'C') movers++; } cur_best = min(cur_best, movers); } table.reverse(); } cout << cur_best << endl; return 0; }