Решение задачи Префиксы с Codeforces

У Николая есть строка s четной длины n, состоящая из латинских букв 'a' и 'b'. Позиции букв пронумерованы от 1 до n.

Он хочет изменить свою строку таким образом, чтобы в любом её префиксе четной длины было поровну букв 'a' и 'b'. Для этого Николай может производить следующую операцию любое количество раз (возможно, нулевое): выбрать позицию в своей строке и заменить букву на этой позиции на другую (то есть заменить букву 'a' на букву 'b' или заменить букву 'b' на букву 'a'). Использовать какие-либо другие буквы, кроме 'a' и 'b', Николай не может.

Префиксом строки s длины l (1≤l≤n) называется строка s[1..l].

Например, для строки s=«abba» существует два префикса чётной длины. Первый из них — это s[1…2]=«ab», второй из них — это s[1…4]=«abba». Оба префикса содержат одинаковое количество букв 'a' и 'b'.

Ваша задача — посчитать минимальное количество операций, которое должен сделать Николай со строкой s, чтобы в любом ее префиксе четной длины строки стало поровну букв 'a' и 'b'.