Zmiennoliterowe słowo

Słowo nazwiemy zmiennoliterowym jeśli każde jego dwie sąsiednie litery są różne. Na przykład słowa mama, ojojoj oraz olimpiada są zmiennoliterowe, zaś anna oraz zorro nie są.

Bajtazar ma swoje ulubione słowo. Niestety, słowo to niekoniecznie jest zmiennoliterowe. Chciałby w nim zakryć niektóre litery, żeby pozostałe litery czytane od lewej do prawej tworzyły słowo zmiennoliterowe. Bajtazar jest mocno przywiązany do swojego ulubionego słowa oraz jest zwolennikiem rozwiązań optymalnych, dlatego chciałby zakryć w swoim słowie jak najmniej liter, żeby otrzymać słowo zmiennoliterowe. Czy pomożesz mu w tym zadaniu?

Napisz program, który wczyta słowo Bajtazara, wyznaczy minimalną liczbę liter, które należy w nim zakryć, aby stało się zmiennoliterowe i wypisze wynik na standardowe wyjście.

W pierwszym (jedynym) wierszu wejścia znajduje się ulubione słowo Bajtazara – niepusty ciąg małych liter alfabetu angielskiego o długości nie przekraczającej 1 000 000 znaków.

W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą – minimalną liczbę liter, które należy zakryć w słowie Bajtazara, aby pozostałe litery czytane od lewej do prawej tworzyły słowo zmiennoliterowe.