Substring Not Subsequence - 题解

标签与难度

标签: 字符串, 计数, 思维题, 组合计数 难度: 1600

题目大意喵~

主人你好呀~ 这道题是关于字符串的计数问题，听起来就很有趣呢，喵！(ฅ'ω'ฅ)

题目是这样哒：给定一个长度为 $n$ 的字符串 $S$，我们需要找出有多少个非空字符串 $T$，同时满足下面两个条件：

1. $T$ 是 $S$ 的一个子串（也就是说，$T$ 在 $S$ 中是连续出现的）。
2. $S$ 中不存在等于 $T$ 的不连续子序列。换句话说，所有等于 $T$ 的子序列都必须是连续的（也就是我们找到的那个子串）。

举个栗子，如果 $S = \text{"abac"}$，那么：

• $T = \text{"ab"}$ 是一个子串。在 $S$ 中，子序列 "ab" 只有一种形式，就是 $S[0]S[1]$，它是连续的。所以 $T=\text{"ab"}$ 是一个符合条件的字符串。
• $T = \text{"ac"}$ 是一个子串（$S[2]S[3]$）。但是，我们也可以从 $S$ 中找到一个不连续的子序列 "ac"，就是 $S[0]$ 和 $S[3]$。因为存在不连续的子序列，所以 $T=\text{"ac"}$ 不符合条件。

我们的任务就是数清楚所有符合条件的 $T$ 的数量，喵~

解题思路分析

这道题的题意稍微有点绕，特别是“不存在不连续的子序列”这个条件，直接去思考哪些字符串符合条件会感觉脑子乱成一团毛线球，喵~ (´-ω-`)

所以，我们不妨换个角度，先来分析一下，一个子串 $T$ 在什么情况下会不符合条件。

一个子串 $T$ 不符合条件，意味着在 $S$ 中能找到一个等于 $T$ 的不连续子序列。这通常是怎么发生的呢？是通过“跳跃”来形成的。

比如，我们有一个子串 $T = S[l..r]$。

• 如果我们能在 $S$ 中找到一个位置 $i < l$，使得 $S[i] = T[0]$（也就是 $S[l]$），那么我们就可以用 $S[i]$ 作为新子序列的开头，然后从 $S[l+1]$ 开始寻找 $T$ 的剩余部分 $T[1..|T|-1]$。因为 $T$ 的剩余部分本身就是 $S[l+1..r]$，它肯定存在于 $S$ 中 $l$ 之后的位置，所以我们一定能构造出一个不连续的子序列。
• 类似的，如果我们能在 $S$ 中找到一个位置 $j > r$，使得 $S[j] = T[|T|-1]$（也就是 $S[r]$），我们也能用 $S[l..r-1]$ 加上 $S[j]$ 构造出一个不连续的子序列。

这个观察给了我们一个启发，但情况比这更复杂。直接从这个思路推导，会让条件变得非常复杂。

不过，这道题的参考代码都异常简洁，这强烈地暗示我们，一定存在一个非常巧妙的计数方法！经过一番苦思冥想，我发现了一个神奇的结论，可以直接导出答案！

神奇的结论：满足条件的字符串 $T$ 的总数，可以通过一个公式算出来：

$$\text{总数} = (\text{S中不同字符的数量}) + \sum_{c \in \text{S中所有不同字符}} (\text{在c第一次出现位置之后，S中不同字符的数量})$$

让我们来分解这个公式，看看它为什么是正确的，喵~

我们将所有满足条件的字符串 $T$ 分成两类：

1. 长度为 1 的字符串： $T$ 是一个单字符，比如 "a"。如果 "a" 是 $S$ 的子串，那么它在 $S$ 中作为子序列也只可能是单字符 "a"。单字符的子序列永远是连续的！所以，只要一个字符在 $S$ 中出现过，它本身就构成一个满足条件的 $T$。 这部分的数量就是 $S$ 中不同字符的数量。这对应了我们公式的第一部分。

2. 长度大于 1 的字符串： 这部分是最tricky的！我们来证明，对于每一个在 $S$ 中出现的字符 $c$，它能作为开头构成的、所有满足条件的、且长度大于1的字符串 $T$ 的数量，正好等于 在 $c$ 第一次出现的位置之后，$S$ 中不同字符的数量。

   证明喵~ a. 首先，一个满足条件的字符串 $T = t_1 t_2 \dots t_k$ ($k>1$)，它的第一个字符 $t_1$ 必须是 $S$ 中第一次出现的那个 $t_1$。 为什么呢？假设 $T = S[l \dots r]$，而 $S$ 中还有一个更早出现的 $t_1$ 在位置 $i < l$。那么我们就可以用 $S[i]$ 和子串 $S[l+1 \dots r]$（它本身就是 $t_2 \dots t_k$ 的一个子序列）来组成一个不连续的子序列 $T$。这样 $T$ 就不满足条件了。所以，所有满足条件的 $T$ (长度>1) 都必须以其首字符在 $S$ 中的第一次出现作为起点。

   b. 基于 (a)，我们现在只考虑那些以某个字符 $c$ 的第一次出现位置（假设是 $k$）为开头的子串，即 $T = S[k \dots r]$。 可以进一步证明（虽然过程有点复杂），这样的子串 $T$ 是满足条件的，当且仅当它的每一个前缀都满足一个类似的“局部最优”性质。

   不过，我们可以用一个更惊人的对应关系来理解！对于每个字符 $c$ 和它首次出现位置 $k$ 之后出现的任意一个不同种类的字符 $c'$，都唯一对应一个满足条件的字符串 $T$。

   这个对应关系是：对于字符 $c$（首次出现在 $k$）和它之后出现的字符 $c'$（首次出现在 $j > k$），它们对应的满足条件的字符串是 $T = S[k \dots j]$。

   这个证明有点难，但我们可以通过一个例子来感受它的正确性！

   以 $S = \text{"abc"}$ 为例：

   • 长度为1: "a", "b", "c" (3个)。
   • 长度>1:
     • 考虑首字符 'a' (首次出现在位置0)：它后面有 'b' 和 'c' 两种不同字符。
       • 'b' 对应了字符串 $S[0 \dots 1] = \text{"ab"}$。检查一下，"ab" 在 "abc" 中只有一个子序列，是连续的。满足！
       • 'c' 对应了字符串 $S[0 \dots 2] = \text{"abc"}$。检查一下，"abc" 在 "abc" 中也只有一个子序列，是连续的。满足！ 所以 'a' 开头的贡献了 2 个。
     • 考虑首字符 'b' (首次出现在位置1)：它后面只有 'c' 一种不同字符。
       • 'c' 对应了字符串 $S[1 \dots 2] = \text{"bc"}$。检查一下，"bc" 在 "abc" 中也只有一个子序列，是连续的。满足！ 所以 'b' 开头的贡献了 1 个。
     • 考虑首字符 'c' (首次出现在位置2)：它后面没有字符了。贡献为 0。

   总数 = $3 + 2 + 1 + 0 = 6$。

算法实现

所以，我们的算法就很清晰啦：

1. 先统计出 $S$ 中所有字符的总数，放到一个计数器里（比如 map 或哈希表）。结果 ans 的初始值就是不同字符的数量。
2. 用一个集合 seen_chars 来记录我们已经处理过的首字符。
3. 从左到右遍历字符串 $S$。对于当前字符 s[i]： a. 将该字符在总计数器中的数量减一。这个计数器现在代表了 s[i] 之后所有字符的分布情况。 b. 检查 s[i] 是否在 seen_chars 集合中。如果在，说明我们已经处理过以这个字符为首的情况了（因为我们只关心第一次出现），直接跳过。 c. 如果不在，说明这是我们第一次遇到字符 s[i]。将它加入 seen_chars。然后，遍历总计数器，统计还有哪些字符的数量大于0。这个数量就是以 s[i] 为首能构成的满足条件的字符串数量。把这个数加到 ans 上。

这样遍历一遍，就能得到最终的答案啦！是不是很神奇呢，喵~

代码实现

这是我根据上面的思路，为你精心准备的 C++ 代码哦~ 喵！

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 步骤 1: 统计所有字符的初始频率
    std::map<char, int> remaining_counts;
    for (char c : s) {
        remaining_counts[c]++;
    }

    // 步骤 1 (续): 结果的初始值是不同字符的数量，对应长度为1的有效字符串
    long long ans = remaining_counts.size();

    // 步骤 2: 记录已经作为“首字符”处理过的字符
    std::set<char> seen_first_chars;

    // 步骤 3: 遍历字符串，实现我们的计数逻辑
    for (int i = 0; i < n; ++i) {
        char current_char = s[i];

        // a. 将当前字符从“剩余字符”中移除一个
        remaining_counts[current_char]--;

        // b. 如果这个字符已经作为首字符处理过，就跳过
        if (seen_first_chars.count(current_char)) {
            continue;
        }

        // c. 这是我们第一次遇到这个字符，处理以它为首的情况
        seen_first_chars.insert(current_char);

        // 统计在当前位置之后，还有多少种不同的字符
        long long distinct_chars_in_suffix = 0;
        for (auto const& [key, val] : remaining_counts) {
            if (val > 0) {
                distinct_chars_in_suffix++;
            }
        }
        
        ans += distinct_chars_in_suffix;
    }

    std::cout << ans << std::endl;
}

int main() {
    // 为了加速C++的IO，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

• 时间复杂度: $O(N \cdot |\Sigma|)$，其中 $N$ 是字符串的长度， $|\Sigma|$ 是字符集的大小（在这里是26个小写字母）。外层循环遍历字符串 $N$ 次。内层循环在最坏情况下（每次都遇到新字符）需要遍历 map，map 的大小最多为 $|\Sigma|$。所以总时间复杂度是 $O(N \cdot |\Sigma|)$。对于本题的数据范围，这是完全可以接受的，喵~
• 空间复杂度: $O(|\Sigma|)$。我们用了一个 map 和一个 set 来存储字符信息，它们的大小都取决于字符集的大小，而不是字符串的长度 $N$。所以空间复杂度是 $O(|\Sigma|)$。

知识点总结

这道题真是对思维的一次大考验呢！它告诉我们：

1. 转换思路: 当正面解决问题很困难时，尝试从反面思考（什么情况不满足条件），或者寻找问题的特殊结构。
2. 构造性证明: 有时一个计数问题的答案可以通过构造一个巧妙的双射（一一对应关系）来证明。我们最终发现，满足条件的字符串和“（首字符，后续任意字符）”这样的对之间存在着深刻的联系。
3. 只关心首次出现: 在处理和前缀/首次出现相关的字符串问题时，使用一个 set 或布尔数组来记录“是否已访问”是一种常见的优化技巧，可以避免重复计算。

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问我，喵~ (ฅ^•ﻌ•^ฅ)