시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

CodingSlave 1.0 is a brand new text editor. There are two possible operations to compose a string in CodingSlave 1.0:

  1. Add one character at the end of the current string.
  2. Choose a nonempty subsequence of the current string and add it at the end of the current string.

Initially, the current string is empty.

Given a word consisting of lowercase English letters, calculate the minimum number of operations needed to compose this string.

입력

The first line contains a string $S$ consisting of lowercase English letters ($1 \le |S| \le 10^6$).

출력

Print one integer: the minimum number of operations needed to compose $S$ using CodingSlave 1.0.

예제 입력 1

aaa

예제 출력 1

3

예제 입력 2

aabaaaabaa

예제 출력 2

5