No.279 木の数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 487
作問者 : 紙ぺーぱー紙ぺーぱー
1 ProblemId : 531 / 出題時の順位表

問題文

kamipeipaa君は木が大好きですが,今日は文字列で遊んでいます。
kamipeipaa君は文字列$S$を並び替えたときに"tree"という部分文字列をいくつ作ることが可能か興味があります。教えてあげてください。

入力

$S$

kamipeipaa君が持つ英字小文字のみからなる文字列$S(1 \le |S| \le 10^{6})$が1行で与えられる。

出力

$S$を自由に並び替えたときに作ることができる"tree"という部分文字列の数の最大値を1行で出力してください。改行を忘れないこと。

サンプル

サンプル1
入力
takahashikunlovesyukicoder
出力
1

"takahashikunlovesyukicoder"を並び替えると"treeakahashikunlovsyukicod"とすることが可能であり、この中に含まれる"tree"という部分文字列は1つです。

サンプル2
入力
treapisnotki
出力
0

"treapisnotki"をどのように並び替えても"tree"という部分文字列を得ることはできません。

サンプル3
入力
eerteerteerteert
出力
4

"eerteerteerteert"という文字列を並び替えると、"treetreetreetree"とすることが可能であり、この中に含まれる"tree"という部分文字列は4つです。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。