19294번 - Dynamic Input Tool 다국어

문제

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.

제한

힌트