Cho xâu kí tự \(s\). Bạn hãy tách xâu \(s\) thành các xâu con liên tiếp sao cho các kí tự ở xâu con là đôi một khác nhau. Ví dụ: \(s = abac\), ta có thể tách thành 2 xâu con \(ab\), \(ac\) hoặc 3 xâu con \(ab\), \(a\), \(c\). In ra số xâu con ít nhất có thể tách được từ \(s\).

INPUT FORMAT

1 dòng gồm 1 xâu kí tự \(s(1 \leq |s| \leq 10^5)\).

OUTPUT FORMAT

In ra số xâu con ít nhất có thể tách được từ \(s\).

Ví dụ:

Input

aaaabbbb

Output

7

Giải thích ví dụ mẫu

Ví dụ

Input:

aaaabbbb

Giải thích: Cần tách xâu thành 7 xâu con: "a", "a", "a", "a", "b", "b", "b", "b", mỗi xâu con chứa một ký tự duy nhất.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House