/* Solution to Game Night by Mees * * Sliding window solution. * * Expected answer: ACCEPTED. * */ #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 i = 0; i < ct[0]; i++) { mismatch[0][table[i] - 'A']++; } for(int i = ct[0]; i < ct[0] + ct[1]; i++) { mismatch[1][table[i] - 'A']++; } for(int i = ct[0] + ct[1]; i < n; i++) { mismatch[2][table[i] - 'A']++; } for(int j = 0; j < n; j++) { cur_best = min(cur_best, mismatch[0][1] + mismatch[0][2] + mismatch[1][0] + mismatch[1][2] + mismatch[2][0] + mismatch[2][1]); mismatch[0][table[j] - 'A']--; mismatch[0][table[ct[0] + j] - 'A']++; mismatch[1][table[ct[0] + j] - 'A']--; mismatch[1][table[ct[0] + ct[1] + j] - 'A']++; mismatch[2][table[ct[0] + ct[1] + j] - 'A']--; mismatch[2][table[j] - 'A']++; } table.reverse(); } cout << cur_best << endl; return 0; }