1951E - 无回文 详细题解

题目大意

给定一个由小写字母组成的字符串 $s$，长度为 $n$，需要将 $s$划分成若干连续子串，满足每个子串都不是回文。 若存在合法划分，输出 YES 并给出任意一种划分方案；否则输出 NO。

约束：

• 测试用例数 $1\le t\le 10^4$
• 单串长度 $1\le |s|\le 10^6$，总长度和 $\sum |s|\le 10^6$
• 要求时间复杂度 $O(n)$ 线性通过

---

核心结论（标程核心思路）

对字符串 $s$ 分四类情况判断，仅两种极端场景无解，其余均存在合法划分：

1. 若 $s$ 本身不是回文 → 直接将整个串作为唯一子串，合法。
2. 若 $s$ 仅由一种字符组成 → 无论如何划分，子串均为回文，无解（输出 NO）。
3. 若 $s$ 是回文且包含至少 $2$ 种不同字符：
   • 找到第一个位置 $t$，满足 $s[t]\neq s[1]$（下标从 $1$ 开始）；
   • 若后缀 $s[t+1,n]$ 不是回文 → 划分为 $s[1,t]$ 和 $s[t+1,n]$，合法；
   • 否则仅两种特殊情况无解，其余划分为 $s[1,t+1]$ 和 $s[t+2,n]$ 即可合法。

---

分情况详细证明与构造

约定

字符串下标从 $1$ 开始，$s[l,r]$ 表示 $s$ 中第 $l$ 到第 $r$ 个字符组成的子串； $n=|s|$ 为字符串长度。

情况1：$s$ 不是回文

直接输出划分 $[s]$，仅 $1$ 个子串，满足条件。 原因：本身非回文，无需分割。

情况2：$s$ 仅由一种字符构成（如 $\texttt{lllllllll}$）

输出 NO。 原因：任意连续子串均为单字符重复，必然是回文，无合法划分。

情况3：$s$ 是回文，且包含至少 $2$ 种不同字符

步骤1：找到关键位置 $t$

设首字符为 $c = s[1]$，找到最小的 $t$，使得：

$$s[t] \neq c$$

由回文性质可知：

$$t \in \left[2,\ \left\lfloor\frac{n+1}{2}\right\rfloor\right] $$

且前缀 $s[1,t]$ 一定不是回文（首字符为 $c$，尾字符非 $c$）。

步骤2：检查后缀 $s[t+1,n]$

• 若 $s[t+1,n]$ 不是回文 划分方案：$[s[1,t],\ s[t+1,n]]$ 两个子串均非回文，合法。

• 若 $s[t+1,n]$ 是回文 此时字符串形态为 $\boldsymbol{A b A b \dots A b A}$，其中 $A$ 由 $t-1$ 个 $c$ 组成，$b\neq c$。 仅两种子情况无解，其余均有解：

子情况3.1：$t = \frac{n+1}{2}$（字符串形态为 $AbA$）

输出 NO。 证明：任意划分中，包含首/尾字符的子串长度至多为 $\frac{n-1}{2}$，必然全为字符 $c$，是回文，无解。

子情况3.2：$t = 2$（字符串形态为 $ABA B \dots ABA$）

输出 NO。 证明：任意划分必存在奇数长度的子串，该子串一定是回文，无解。

子情况3.3：其余情况（$2 < t < \frac{n+1}{2}$）

划分方案：$[s[1,t+1],\ s[t+2,n]]$ 证明：

• $s[1,t+1]$ 前 $t-1$ 个字符为 $c$，最后 $1$ 个字符为 $c$，中间为非 $c$ 字符 → 非回文；
• $s[t+2,n]$ 前 $t-2$ 个字符为 $c$，最后 $t-1$ 个字符为 $c$ → 非回文； 两个子串均合法，划分有效。

---

实现要点

1. 回文判断：线性判断字符串是否为回文，$O(n)$；
2. 找关键位置 $t$：遍历字符串找第一个与首字符不同的位置，$O(n)$；
3. 划分构造：根据上述情况直接切割字符串，无额外复杂度；
4. 总复杂度：$O(n)$ per test case，满足题目数据范围。

---

标程核心逻辑伪代码

bool is_palindrome(string &s) {
    int n = s.size();
    for(int i=0; i<n/2; i++)
        if(s[i]!=s[n-1-i]) return 0;
    return 1;
}

bool is_all_same(string &s) {
    char c = s[0];
    for(auto ch : s) if(ch!=c) return 0;
    return 1;
}

void solve() {
    string s; cin >> s;
    int n = s.size();
    // 情况1：本身非回文
    if(!is_palindrome(s)) {
        cout << "YES\n1\n" << s << '\n';
        return;
    }
    // 情况2：全同字符
    if(is_all_same(s)) {
        cout << "NO\n";
        return;
    }
    // 情况3：回文+多字符，找t
    int t = 1;
    while(t < n && s[t] == s[0]) t++;
    string a = s.substr(0, t);
    string b = s.substr(t);
    // 后缀非回文
    if(!is_palindrome(b)) {
        cout << "YES\n2\n" << a << ' ' << b << '\n';
        return;
    }
    // 两种NO情况
    int mid = (n+1)/2;
    if(t == mid || t == 2) {
        cout << "NO\n";
        return;
    }
    // 划分成 t+1 和 剩余
    string p1 = s.substr(0, t+1);
    string p2 = s.substr(t+1);
    cout << "YES\n2\n" << p1 << ' ' << p2 << '\n';
}

---

复杂度分析

• 时间复杂度：$O(\sum n)$，线性遍历，无冗余计算；
• 空间复杂度：$O(n)$，仅存储字符串与划分结果，符合 $256\text{MB}$ 内存限制。