【题目来源】
https://www.acwing.com/problem/content/4893/
【题目描述】
给定一个字符串，其中的每个字符要么是 M，要么是 O。
你可以通过以下操作将该字符串变为 MOO：
改变字符串中的第一个或最后一个字符（M 变为 O，O 变为 M）。
删除字符串中的第一个或最后一个字符。
请你计算，为了将给定字符串变成 MOO，所需要的最少操作次数。
【输入格式】
第一行包含整数 Q，表示共有 Q 组测试数据。
每组数据占一行，包含一个字符串，其中的每个字符要么是 M，要么是 O。
【输出格式】
每组数据输出一行结果，一个整数，表示所需要的最少操作次数。如果无解，则输出 -1。
【数据范围】
1≤Q≤100,
每个字符串的长度范围 [1,100]。
【输入样例】
3
MOMMOM
MMO
MOO
【输出样例】
4
-1
0
【样例解释】
第一个字符串 MOMMOM 变为 MOO 最少需要 4 步操作，一种可行方案为：
将最后一个字符变为 O。
删除第一个字符。
删除第一个字符。
删除第一个字符。
第二个字符串无法变为 MOO。
第三个字符串已经是 MOO，无需任何操作。
【算法分析】
★ s.substr(pos,len)：返回字符串 s 中从 pos 开始的 len 个字符的子串
#include <bits/stdc++.h>
using namespace std;int main() {string s;cin>>s;for(int i=0; i<s.size()-2; i++) {string t=s.substr(i,3);cout<<t<<endl;}return 0;
}/*
in:
abcdefgout:
abc
bcd
cde
def
efg
*/★ 样例分析
首先字符串至少要有 3 位，没有直接输出 -1。
我们三位三位模拟取最小值，只要中间是 O，都可以变成 MOO。也就是说，由M和O组成的三位字符串虽然有“OOO、OOM、OMO、OMM、MOO、MOM、MMO、MMM”等8种组合，但通过题目给出的两种操作，能变为MOO的初始字符串只能是含有“MOO、MOM、OOO、OOM”等四种子串的字符串。
操作次数如下：
MOO：0 次。
MOM：1 次。
OOO：1 次。
OOM：2 次。
最终取最小值加上总长度 -3 即可。因为最终只能保留 3 位。如果 t 仍是初始值，那么输出 -1。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int inf=0x3f3f3f3f;int main() {int T;cin>>T;while(T--) {string s;cin>>s;if(s.size()<3) {cout<<"-1"<<endl;continue;}int t=inf;for(int i=0; i<s.size()-2; i++) {string sub=s.substr(i,3);if(sub=="MOO") t=min(t,0);else if(sub=="MOM") t=min(t,1);else if(sub=="OOO") t=min(t,1);else if(sub=="OOM") t=min(t,2);}if(t==inf) cout<<"-1"<<endl;else cout<<t+s.size()-3<<endl;}return 0;
}/*
in:
3
MOMMOM
MMO
MOOout:
4
-1
0
*/
【参考文献】
https://www.acwing.com/solution/content/172013/
