No.279 木の数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 546
作問者 : 紙ぺーぱー紙ぺーぱー
3 ProblemId : 531 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:48:59

問題文

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つです。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。