시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB22201890.000%

문제

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.

예제 입력 1

shellless

예제 출력 1

3

Wyjaśnienie do przykładu: W słowie shellless (które z języka angielskiego można tłumaczyć jako „bez skorupy” lub „pozbawiony skorupy”) możemy na przykład zakryć dwie litery l na czwartej i piątej pozycji oraz ostatnią literę s, aby otrzymać słowo sheles, które jest zmiennoliterowe.

예제 입력 2

bajtazar

예제 출력 2

0

Wyjaśnienie do przykładu: Słowo bajtazar jest już zmiennoliterowe, więc nic nie trzeba w nim zakrywać.

예제 입력 3

zwolennikrozwiazanoptymalnych

예제 출력 3

1

Wyjaśnienie do przykładu: Wystarczy zakryć jedną z sąsiadujących liter n we fragmencie zwolennik.

예제 입력 4

xxxxxxxxxxx

예제 출력 4

10

Wyjaśnienie do przykładu: W tym przypadku należy zakryć wszystkie litery poza jedną.