NOIOI 塔
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
NOIOI 塔是一种单人游戏。
这个游戏要用到一些写有 N, O, I 中任一文字的圆盘。这些圆盘的直径互不相同。游戏开始时,这些圆盘按照直径大的在下面的规则堆叠。你需要用这些圆盘做尽量多的迷你 NOIOI 塔。迷你 NOIOI 塔由 个圆盘构成,从直径较小的圆盘开始分别为 N, O, I 或分别为 I, O, I 。不过,每个圆盘最多只能使用一次。

给出长为 的字符串 ,表示直径从小到大的圆盘上的文字。请编写程序求出使用这些圆盘能够做出的迷你 NOIOI 塔个数的最大值。
输入格式
第一行为一个整数 ,表示字符串 的长度。
第二行是一个字符串 。
输出格式
一行一个整数:表示能够做出的迷你 NOIOI 塔数量的最大值。
输入输出样例 #1
输入 #1
6
NOIIOI
输出 #1
2
输入输出样例 #2
输入 #2
5
NOIOI
输出 #2
1
输入输出样例 #3
输入 #3
6
NOIOII
输出 #3
2
输入输出样例 #4
输入 #4
15
NNOIIOONONIOIIO
输出 #4
4
输入输出样例解释
样例 1
NOIIOI 分别含子串 NOI 和子串 IOI 各一个,故可以做出 2 个迷你 NOIOI 塔。
样例 2
虽然 NOIOI 也分别含子串 NOI 和子串 IOI 各一个,但每个字符不能被使用两次或以上。
样例 3
对应题目描述中给出的例子。
数据范围
子任务捆绑测试。对于所有数据,。
| 子任务 | 分值 | |
|---|---|---|