官方题解（中文整理）

基于 Nick Wu 的官方题解整理。

三个基本观察

先做三个非常重要的观察。

第一，平方串的长度一定是偶数，所以每次删除的子序列长度也一定是偶数。要把整个字符串删空，总长度 \(3N\) 必须是偶数，也就是说 \(N\) 必须是偶数；若 \(N\) 为奇数，答案直接是 -1。

第二，判断是否能用 \(1\) 次操作完成非常简单：只需要检查 \(S\) 的前半部分是否与后半部分完全相同。若相同，则整个 \(S\) 本身就是一个平方串。

第三，只要可行，其实最多只需要 \(2\) 次操作；而即使不利用这个结论，也总能在 \(3\) 次内完成。原因是当 \(N\) 为偶数时，字符串中 C、O、W 的个数都恰好是偶数，因此可以分别用三次操作删掉全部 C、全部 O、全部 W。

题目的难点在于：什么时候能做到 \(2\) 次。

为什么可行时一定能在两次内完成

把整个字符串平均分成两半，每半长度都是 \(\frac{3N}{2}\)。由于 \(N\) 为偶数，所以这两半都正好由若干个长度为 \(3\) 的块组成。

现在看任意一对对应的长度为 \(3\) 的块。每个块都只能是：

• COW
• OWC
• WCO

对于这三种字符串的任意两种，最长公共子串长度都至少为 \(2\)。于是对于每一对对应块，我们总能做出如下划分：

• 从左半块和右半块中，各取出一个相同的长度为 \(2\) 的子串，放进第 1 次操作；
• 剩下的字符放进第 2 次操作。

如果两个块本身完全相同，那么这 \(6\) 个字符甚至都可以直接放进第 1 次操作。

把所有对应块都这样处理后：

• 第 1 次操作选出的子序列，其左半部分与右半部分完全相同，因此是平方串；
• 第 2 次操作选出的子序列也同理是平方串。

所以，只要 \(N\) 是偶数，就一定可以在最多 \(2\) 次操作内删空。

如何输出构造

如果前半串和后半串完全相同，那么直接输出 \(M=1\)，并令每个位置都属于第 \(1\) 次操作。

否则输出 \(M=2\)。然后按块处理每一对对应的长度为 \(3\) 的字符串：

• 找到它们可以对齐的公共长度 \(2\) 子串；
• 这四个字符标记为第 \(1\) 次操作；
• 剩下两个字符标记为第 \(2\) 次操作。

这样得到的两个操作一定都合法。

关于参数 \(k\)

因为可行时最优值一定是 \(1\) 或 \(2\)：

• 当 \(k=0\) 时，上述做法能给出最优解；
• 当 \(k=1\) 时，同样直接输出最优解当然也满足要求。

复杂度

每个测试只需线性扫描整串，时间复杂度 \(O(N)\)。