「みんなのプロコン」本選 オープンコンテスト

A - YahooYahooYahoo


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 400

問題文

高橋君は,文字列 S を持っています. 高橋君は yahoo という文字列が好きなので,S を編集することで yahoo の繰り返しで得られる文字列に変えようとしています. ここで,yahoo の繰り返しで得られる文字列とは,yahoo0 個以上つなげてできる文字列です.これらは,短いほうから順に (空文字列),yahooyahooyahoo,… となります.

高橋君は 1 回の操作で次のうちいずれかを行うことができます.

  • S の任意の 1 文字を選んで,それを任意の英小文字に書き換える.
  • S の任意の 1 文字を選んで,その文字を S から取り除く.
  • S の任意の位置に,任意の英小文字を挿入する.

高橋君が Syahoo の繰り返しで得られる文字列にするために,必要な操作の回数の最小値を求めてください.

制約

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

入力

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

S

出力

高橋君が Syahoo の繰り返しで得られる文字列にするために,必要な操作の回数の最小値を求めてください.


入力例 1

yfoo

出力例 1

2

例えば,次のようにすればよいです.

  • 2 文字目の fh に変える.Syhoo になる.
  • 1 文字目と 2 文字目の間に a を挿入する.Syahoo になる.

入力例 2

z

出力例 2

1

1 文字目の z を取り除くと,S は空文字列になり,yahoo の繰り返しで得られる文字列になります.


入力例 3

yahooyahooyahooyahooyahoo

出力例 3

0

入力例 4

yahyahoo

出力例 4

2

Submit提出する