噜噜的 DTOJ 挑战

题目背景

噜噜最近在刷 DTOJ 上的题目。

有一天他发现了一串神秘的字符序列，据说里面隐藏着很多个 "dtoj"。

不过这些 "dtoj" 并不是连续出现的，而是需要按照一定规则从字符串中挑选出来。

为了证明自己的算法实力，噜噜决定计算：

这串字符中 最多能挑出多少个 "dtoj"。

现在请你帮助噜噜完成这个任务。

题目描述

给定一个仅包含 小写字母 的字符串 $S$。

你需要从中挑选若干组字符，使其组成字符串：dtoj

挑选必须满足以下规则：

挑选规则

1. 每次必须选出 恰好 4 个字符。
2. 这 4 个字符必须按顺序组成：d → t → o → j
3. 所选字符在原字符串中的 相对顺序必须保持不变（即形成子序列）。
4. 每个字符最多只能使用一次。

你的任务是求出：

最多可以组成多少个 "dtoj"。

输入格式

输入一行字符串：$S$,字符串只包含小写字母。

输出格式

输出一个整数，表示最多可以组成的 "dtoj" 的数量。

dtojtdooj

1

说明

可以从字符串中依次选出：

共1组 "dtoj"。

adtootjodtoj

2

说明

可以通过 跳跃选取字符 形成 "dtoj"，只要：

• 顺序满足 d → t → o → j

• 每个字符只使用一次

即可。

限制