Божевільний вчений

Фермер Джон впорядкував $n$ своїх корів, кожна з яких належить до однієї з двох порід: Holsteins або Guernseys. Він зафіксував цей порядок у вигляді рядка з $n$ символів, кожен з яких дорівнює або $H$, або $G$ відповідно. Однак, на жаль, коли корови прибули на ферму і Джон знову вишикував їх у ряд, отриманий рядок виявився відмінним від початкового.

Позначимо ці два рядки через $a$ та $b$, де $a$ — початковий рядок, який Фермер Джон хотів побачити, а $b$ — рядок, що отримався після прибуття корів. Фермер Джон звернувся за допомогою до свого кузена Бена.

Після кількох місяців роботи Бен створив дивовижну машину MCBF-3000, яка вміє вибирати будь-яку підстроку і замінювати в ній всі символи $G$ на $H$, а всі символи $H$ — на $G$. Тепер Фермер Джон хоче дізнатися мінімальну кількість застосувань цієї машини, необхідну для перетворення рядка $b$ у рядок $a$. Допоможіть Фермеру Джону розв'язати цю задачу.