喵~ 主人，你好呀！今天我们来看一道非常有趣的字符串问题，1791D - Distinct Split。这道题就像是把一根美味的鱼分成两段，要让两段的美味程度加起来最高！是不是很有意思呢？别担心，这道题并不难，让本猫娘一步一步带你解开它吧，喵~

题目大意

这道题是这样哒：

首先，我们定义一个函数 f(x)，它的功能是计算字符串 x 中有多少个 不同 的字符。比如说：

• f("abc") = 3，因为有 'a', 'b', 'c' 三个不同的字符。
• f("bbbbb") = 1，因为只有一个 'b'。
• f("babacaba") = 3，因为有 'a', 'b', 'c' 这三个。

然后，题目会给我们一个字符串 s。我们需要把 s 切成两个 非空 的部分，我们叫它们 a 和 b，拼接起来要正好等于 s (也就是 a+b=s)。

我们的任务是，找到一种切割方法，使得 f(a) + f(b) 的值最大。输出这个最大的值就可以啦，喵！

举个例子，如果 s = "abcabcd"：

• 我们可以切成 a = "a" 和 b = "bcabcd"。f(a)=1, f(b)=4，和是 1+4=5。
• 我们也可以切成 a = "abc" 和 b = "abcd"。f(a)=3, f(b)=4，和是 3+4=7。
• ...还有很多种切法。

我们需要遍历所有可能的切法，找到那个能让 f(a) + f(b) 最大的结果。在这个例子里，7 就是最大的啦~

解题思路

要找到最大的 f(a) + f(b)，最直接的想法就是尝试所有可能的分割点，对吧？

一个长度为 n 的字符串 s，可以有多少个分割点呢？ 我们可以从第1个字符后分割，第2个字符后分割，...，一直到第 n-1 个字符后分割。总共有 n-1 个可能的分割点。

对于每一个分割点 i (我们把字符串索引看作从 0 开始)，字符串 s 被分成了两部分：

1. 前缀 a = s[0...i]
2. 后缀 b = s[i+1...n-1]

如果我们对每个分割点 i，都去计算一次 f(s[0...i]) 和 f(s[i+1...n-1])，然后相加，再取所有结果中的最大值，理论上是可行的。

但是，每次都重新计算 f(a) 和 f(b) 会不会太慢了呀？(挠头) 如果字符串很长，比如 n = 2*10^5，每次计算一个子串的不同字符数需要 O(n) 的时间，总共 n-1 个分割点，总时间复杂度就是 O(n^2)，这肯定会超时的，呜...

所以，我们需要一个更聪明的办法！预处理！这就像猫猫提前藏好小鱼干，想吃的时候就能立刻找到，嘿嘿~

我们可以创建两个数组，来提前存好我们需要的信息：

1. prefix_distinct[i]：记录前缀 s[0...i] 中不同字符的数量。
2. suffix_distinct[i]：记录后缀 s[i...n-1] 中不同字符的数量。

这两个数组怎么高效地计算出来呢？

• 计算 prefix_distinct：我们从左到右遍历字符串 s。用一个大小为26的布尔数组 seen 来记录 'a' 到 'z' 是否出现过。每遍历到一个新字符，如果它没在 seen 里出现过，我们就把 distinct_count 加一，并标记它为已出现。prefix_distinct[i] 的值就是当前 distinct_count 的值。这样一次遍历 O(n) 就能搞定。
• 计算 suffix_distinct：同理，我们从右到左遍历字符串 s，用一个新的 seen 数组，做同样的事情。这样 O(n) 也能搞定。

有了这两个数组之后，事情就变得超级简单啦！我们再遍历一次所有可能的分割点 i（从 0 到 n-2）。对于每个分割点 i：

• 左边部分 a = s[0...i] 的不同字符数就是 prefix_distinct[i]。
• 右边部分 b = s[i+1...n-1] 的不同字符数就是 suffix_distinct[i+1]。

我们要计算的值就是 prefix_distinct[i] + suffix_distinct[i+1]。我们只需要一个循环，找到所有这些和中的最大值就好啦！

整个算法的流程就是：

1. 计算 prefix_distinct 数组 (O(n))。
2. 计算 suffix_distinct 数组 (O(n))。
3. 遍历分割点，查找最大和 (O(n))。

总时间复杂度是 O(n)，非常快，一定能通过的，喵~

题解代码详解

让我们一起来看看这份简洁优雅的代码吧！

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

// 处理单个测试用例的函数
void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // prefix_distinct[i] 存的是 s[0...i] 中不同字符的数量
    std::vector<int> prefix_distinct(n);
    std::vector<bool> seen(26, false); // 用来追踪见过哪些字符 ('a'-'z')
    int distinct_count = 0;
    for (int i = 0; i < n; ++i) {
        int char_idx = s[i] - 'a'; // 把字符转换成 0-25 的索引
        if (!seen[char_idx]) { // 如果这个字符是第一次见
            seen[char_idx] = true; // 标记为见过
            distinct_count++; // 不同字符数+1
        }
        prefix_distinct[i] = distinct_count; // 存入数组
    }

    // suffix_distinct[i] 存的是 s[i...n-1] 中不同字符的数量
    std::vector<int> suffix_distinct(n);
    std::fill(seen.begin(), seen.end(), false); // 重置 seen 数组，准备从右往左扫
    distinct_count = 0;
    for (int i = n - 1; i >= 0; --i) {
        int char_idx = s[i] - 'a';
        if (!seen[char_idx]) {
            seen[char_idx] = true;
            distinct_count++;
        }
        suffix_distinct[i] = distinct_count;
    }

    int max_val = 0;
    // 遍历所有可能的分割点
    // 分割点在索引 i 之后，产生 s[0...i] 和 s[i+1...n-1]
    for (int i = 0; i < n - 1; ++i) {
        // 直接从预处理的数组里取值，是不是超快！
        int current_val = prefix_distinct[i] + suffix_distinct[i + 1];
        max_val = std::max(max_val, current_val); // 更新最大值
    }

    std::cout << max_val << "\n";
}

int main() {
    // 快速 I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码的逻辑和我们刚才分析的思路一模一样，对不对？先用两个循环预处理出前缀和后缀的不同字符数，最后再用一个循环找到最大值。非常清晰明了，喵！

知识点介绍

这道题用到的核心思想，在算法竞赛中可是非常有用的哦！

1. 前缀/后缀预处理 (Prefix/Suffix Precomputation) 这个思想和“前缀和”很像。标准的前缀和是用来快速计算一个数组区间内所有元素的和。而在这里，我们不是求和，而是求“不同元素的个数”。但原理是相通的：通过一次线性扫描，预先计算出所有前缀（或后缀）的某些性质，从而可以在 O(1) 的时间内查询任何一个前缀（或后缀）的该性质。 这种“空间换时间”的策略，能把很多 O(n^2) 的暴力枚举问题优化到 O(n)，是每个想要变强的算法爱好者都必须掌握的技巧哦！

2. 频率数组/哈希 (Frequency Array/Hashing) 为了快速判断一个字符是否已经出现过，我们用了一个大小为26的布尔数组 seen。因为题目中的字符都是小写英文字母，种类有限且固定，所以用一个数组，把 s[i] - 'a' 作为下标，就能直接映射到数组的对应位置。这比用 std::set 或者 std::map 更简单，也更快！这种方法通常被称为频率数组或桶计数，是处理字符统计问题的常用手段。

好啦，今天的讲解就到这里啦！希望本猫娘的解释能帮到你，喵~ 如果还有什么问题，随时可以再来问我哦！祝你刷题愉快！