Implementation outline

We enumerate all the substrings \(t\) of \(S\), compute the filling rate for each \(t\), and take the maximum value.

After initializing \(f\) with \(0\), perform the following operation for every substring.

• Find the filling rate of the string \(r\) as follows.
  • \(0\) if \(|t| < 3\).
  • \(0\) if \(t\) does not start with t.
  • \(0\) if \(t\) does not end with t.
  • Otherwise, find the number of ts occurring in \(t\), and evaluate \(\frac{x-2}{|t|-2}\).
• Determine if the filling rate computed above is greater than \(f\). If it is, set \(f\) to that value.

There are \(\Theta(N^2)\) substrings, and computing the filling rate costs \(O(N)\) time per substring, so the overall time complexity is \(O(N^3)\), which is fast enough.

Sample code (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;
}