実装方針

\(S\) の部分文字列を列挙し，各部分文字列 \(t\) について充填率を求めてそれらの最大値をとる実装方針をとります．

\(f\) を \(0\) で初期化したあと，すべての部分文字列について以下の手順を実行すればよいです．

• 文字列 \(t\) の充填率を以下の手順で求める．
  • \(|t| < 3\) の場合，\(0\)．
  • \(t\) の先頭の文字が t でない場合，\(0\)．
  • \(t\) の末尾の文字が t でない場合，\(0\)．
  • 上のいずれにも当てはまらない場合，\(t\) に含まれる t の個数 \(x\) を求め，\(\frac{x-2}{|t|-2}\) を計算する．
• 上で求めた充填率が \(f\) よりも大きいかを判定し，大きいならば \(f\) をその値に更新する．

部分文字列は \(\Theta(N^2)\) 通りあり，充填率の計算には \(O(N)\) 時間かかるので，全体の時間計算量は \(O(N^3)\) となり，十分高速です．

実装例 (C++)

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <iomanip>
#include <limits>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::string;

string s;

void solve () {
	int n = s.size();
	long double ans = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] != 't') continue;

		for (int j = i + 2; j < n; j++) {
			if (s[j] != 't') continue;

			int x = 0;
			for (int ki = i; ki <= j; ki++) {
				if (s[ki] == 't') x++;
			}
			int len = (j - i + 1);

			long double item = (long double)(x - 2) / (long double)(len - 2);
			if (item > ans) ans = item;
		}
	}

	cout << std::fixed << std::setprecision(17) << ans << "\n";

	return;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> s;

	solve();

	return 0;
}