Zmiennoliterowe słowo
면접 대비시간 제한4초메모리 제한1024 MB
남은 인접 문자가 서로 다르도록 문자열에서 지울 문자의 최소 개수를 구한다.
문제
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.