#1860. 三连T

三连T

题目描述

小 A 特别喜欢字母 T,尤其是连续出现三个 T 的模式 TTT。

现在给定一个只由大写字母组成的字符串 ss。小 A 最多可以修改其中一个字符,把它改成任意大写字母,也可以选择不修改。

修改之后,字符串中每一个连续出现的 TTT 都称为一个好模式。子串允许重叠,例如 TTTT 中含有两个 TTT。

请你帮小 A 计算,修改后最多能得到多少个 TTT。

输入格式

一行一个字符串 ss,仅由大写英文字母组成。

输出格式

输出一行一个整数,表示最多能得到的 TTT 子串数量。

样例

TTTBCDTTT
3
TTXT
2
ABC
0

样例解释

样例 1 中,原串已经有第 1∼31\sim3 位和第 7∼97\sim9 位两个 TTT。把第 44 位的 B 改成 T 后得到 TTTTCDTTT,其中 TTTT 贡献两个、末尾再贡献一个,共 33 个。

样例 2 中,把 X 改成 T 得到 TTTT,其中有两个可重叠的 TTT。

样例 3 中,原串不含 T,只修改一个字符最多只能得到一个 T,无法组成 TTT,所以答案是 00。

数据范围与约定

子任务 分值 限制
11 3030 1≤∣s∣≤10001 \le \lvert s \rvert \le 1000
22 7070 无额外限制

对于 100%100\% 的数据,保证 1≤∣s∣≤1051 \le \lvert s \rvert \le 10^5,且 ss 仅由大写英文字母组成。