給定長度為 \(n\) 的字符串 \(s\)，問至多能將 \(s\) 劃分成多少個子序列，使得每個子序列都不是回文串？（輸出方案）

特殊性質 A：每個字符出現次數不超過 \(\frac{n}{2}\)。

特殊性質 B：只有 a, b 兩種字符。

這個題沒有特殊性質提示感覺有紫。

特殊性質 A

沒有絕對眾數，所以可以嘗試把兩個不同的字符丟到一個回文串，答案為 \(\lfloor \frac{n}{2} \rfloor\)。

構造有個經典 trick，將 \(s\) 重排，顏色相同的丟一起，然后 \((i, i + n / 2)\) 形成一個子序列。\(n\) 是奇數丟到 \((1, 1 + n / 2)\) 里即可。

特殊性質 B

不妨設 a, b 中多的為 a，其數量 \(c_a\) 達到了 \(\lfloor \frac{n}{2} \rfloor\)。

顯然每個字符串里都要有 b，所以答案至多 \(c_b\)。

考慮如何達到這個上界，有兩種顯然不是回文串的字符串 aa...ab 及 baa...a。設 b 的出現位置是 \(p_1, p_2, \dots p_{c_b}\)。

• 對于 \(1 < i < c_b\)，\(p_{i - 1} + 1 \sim p_i\) 組成一個子序列。
• 對于 \(i = 1\)，讓 \(p_1, p_{c_b - 2} + 1 \sim p_{cb - 1} - 1, p_{cb - 1} + 1 \sim n\) 組成一個子序列。
• 對于 \(i = c_b\)，讓 \(1 \sim p_1 - 1, p_{c_b}\) 組成一個子序列。

這樣構造能使得每個字符串都是前面的兩種形式。對于那些只有一個字符 b 的子序列，從別的子序列挪一個 a 形成 ab 或 ba。

正解

把兩部分結合起來，如果有絕對眾數，把絕對眾數視為 a，剩下的視為 b，做特殊性質 B。否則特殊性質 A。

時間復雜度：\(O(n)\)。

這個題特殊性質有較強的引導意義，特殊性質 A 的 trick 值得學一下。這種分是否有絕對眾數討論的思想值得學習。

性質 B 的構造也需要想想，抓到很不是回文串的兩種字符串即可。