简要题意

有 $Q$ 个询问，对于每个询问，给你一个只含有字符“M”和字符“O”的字符串 $S$，求最少要几次操作 $^{[1]}$，使字符串 $S$ 变成字符串“MOO”。

操作 $^{[1]}$：四种操作

• 1.将字符串第一个字符取反（即：“M”变成“O”，“O”变成“M”）

• 2.将字符串最后一个字符取反（即：“M”变成“O”，“O”变成“M”）

• 3.删除字符串第一个字符

• 4.删除字符串最后一个字符

思路

首先要确认所有不可能经过操作后变成“MOO”的字符串，最容易看出来的是字符串长度 l < 3，另一个不可能变成“MOO”的就是在字符串第二个字符到字符串倒数第二个之间没有任何字符“O”的字符串，因为在四种操作中没有任何对中间字符的修改，而且因为每次删除的都是左右两侧的字符，所以最终得到的字符串一定是原字符串中连续的长度为三的一个子串，如果子串中间不是“O”，就不能变成“MOO”。

然后再来确认最小的操作次数，因为最终得到的字符串一定是原字符串中连续的长度为三的一个子串，所以我们只需要枚举第一个字符就行了，如果枚举到的字符的下一个字符不是“O”就跳过，如果是“O”就计算需要改正的次数，将 ans 更新。

最后 $ans$ 不要忘了加上 $l-3$，因为无论怎么删，都要至少把字符串的长度变成 $3$ 此时一共操作了 $l-3$ 次！

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
bool check(string s, int l, int r ) { //用于检测是否存在中间含O的连续串
	for(int i = l; i <= r; i++) 
		if(s[i]=='O') return true;
	return false;
}
void slove() {
	string s;  int ans = 105; //注意这里的初始化
	cin >> s; 
	int len = s.size();
	if(len < 3 || !check(s,1,len-2)){ //两种不行的情况
		cout << -1 << endl;
		return;
	}
	//一定有解，找到最接近MOO格式的，看看连续的三个字母
	for(int i = 0; i <= len-3; i++) {
		if(s[i+1]=='M') continue;	//分别是s[i],s[i+1],s[i+2],中间为M不考虑
		int x = (s[i]=='O')+(s[i+2]=='M'); //前后转为MOO的代价
		ans = min(ans, x);
	}
	ans += len-3; //去掉多余的字符，删除
	cout << ans << endl;
}

int main() {

	int _ = 1;
	cin >> _;
	while(_--) {
		slove();
	}
	return 0;
}