只考虑常数字符集，所以关于字符集的复杂度都没算进来。
最少非回文子串划分
答案是 \(1\) 或 \(2\) 或者无解，参考 CF1951E 的题解。
时间复杂度：\(\mathcal O(n)\)。
最少非回文子序列划分
考虑最少非回文子串划分的情况，可以发现答案是 \(2\) 的情况也不可能划分成 \(1\) 个子序列，所以和上面是一样的。
时间复杂度：\(\mathcal O(n)\)。
最少回文子串划分
容易有一个 \(\mathcal O(n^2)\) dp，这个 dp 可以用 PAM slink 优化 做到 \(\mathcal O(n\log n)\)。参考做法是 CF932G，这个题是数偶回文划分的方案数（当然要先用一步倒着间隔插的 trick 把 border 划分转回文划分），可以直接改成数回文划分的 \(\min\)。
网上介绍这个的资料很多。
时间复杂度：\(\mathcal O(n\log n)\)。
最少回文子序列划分
这个真的有小于指数级的做法吗……
最多非回文子串划分
贪着做，两个字符不相同就在后一个字符后面划一下，这样最后可能会剩下一段，前面的都形如 \(\texttt{aaaaa}\cdots\texttt{b}\)。显然这样做是上界，因为一个非回文子串至少需要两个不同的字符。
这样的问题是最后一段不一定能合进去还保证最后一个串非回文。你考虑倒着再做一遍。如果还不行的话就要考虑调整方案了。
此时可以发现，最后三个划分合并在一起一定要么不是回文串，要么不可能是一个除中间外都相同的 \(\texttt{aaabaaa}\) 式的回文串，按照最少非回文串划分的结论，这种一定回文串一定可以切分成两个非回文串，所以答案就减掉一。
大概需要特判一下初始划分数 \(\le 2\) 的情况。
时间复杂度：\(\mathcal O(n)\)。
最多非回文子序列划分
时间复杂度：\(\mathcal O(n)\)。
最多回文子串划分
奶龙题，输出 \(n\)。
时间复杂度：\(\mathcal O(1)\)。
最多回文子序列划分
奶龙题，输出 \(n\)。
时间复杂度：\(\mathcal O(1)\)。
标签：子串,复杂度,八重,划分,最少,mathcal,回文 From： https://www.cnblogs.com/lemonniforever/p/18493236