#P4873. 哞操作
-
ID: 3760
传统题
1000ms
128MiB
尝试: 8
已通过: 2
难度: 10
上传者:
哞操作
Description
给定一个字符串，其中的每个字符要么是 M，要么是 O。
你可以通过以下操作将该字符串变为 MOO：
- 改变字符串中的第一个或最后一个字符（M 变为 O，O 变为 M）。
- 删除字符串中的第一个或最后一个字符。
请你计算，为了将给定字符串变成 MOO，所需要的最少操作次数。
Input Format
第一行包含整数 Q，表示共有 Q 组测试数据。每组数据占一行，包含一个字符串，其中的每个字符要么是 M，要么是 O。
1≤Q≤100,
每个字符串的长度范围 [1,100]。
Output Format
每组数据输出一行结果，一个整数，表示所需要的最少操作次数。如果无解，则输出 -1。3
MOMMOM
MMO
MOO4
-1
0Hint
第一个字符串 MOMMOM 变为 MOO 最少需要 4 步操作，一种可行方案为：
- 将最后一个字符变为 O。
- 删除第一个字符。
- 删除第一个字符。
- 删除第一个字符。
第二个字符串无法变为 MOO。
第三个字符串已经是 MOO，无需任何操作。
