D - Concatenation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

英小文字から成る文字列 S が与えられます。

これは code のように、先頭の文字がその文字列においてアルファベット順で最小となる文字列を1つ以上連結してできたものです。

元となるそれぞれの文字列には、先頭と同じ文字が複数含まれていたことはありません。

S は最小で何個の文字列を繋げてできた可能性があるでしょうか。

制約

  • 1 \leq |S| \leq 10^5
  • S は英小文字から成る

入力

入力は以下の形式で標準入力から与えられる。

S

出力

連結して S になるような題意の文字列の個数の最小値を出力せよ。


入力例 1

codethanksfes

出力例 1

2

例えば codethanksfes を連結するとできます。


入力例 2

atcoder

出力例 2

1

atcoder は条件を満たします。


入力例 3

aaa

出力例 3

3