Crazy Binary String - 题解

标签与难度

标签: 前缀和, 哈希表, 字符串, 思维, 线性时间复杂度难度: 1500

题目大意喵~

你好呀，未来的算法大师！这道题是关于 ZYB 同学最喜欢的二进制字符串的，喵~

题目给了我们一个只包含 '0' 和 '1' 的字符串 T。我们需要完成两个小任务：

找到 T 的一个子串 (substring)，这个子串里的 '0' 和 '1' 数量必须相等，并且我们想让这个子串的长度尽可能地长！
找到 T 的一个子序列 (subsequence)，同样，这个子序列里的 '0' 和 '1' 数量也必须相等，并且长度也要尽可能地长！

最后，把这两个最长长度告诉 ZYB 就好啦。

举个例子，如果 T = "01101":

子串是连续的一部分，比如 "01", "110"。其中 "10" 是一个 '0'、'1' 数量相等的子串，长度为 2。"0110" 也是，长度为 4。最长的就是 "0110"，长度是 4。
子序列可以不连续，只要保持原有的先后顺序就行。比如从 "01101" 里可以挑出第一个 0 和最后一个 1 组成 "01"。

我们要找的就是这两个任务的最优解，也就是最大的长度，喵~

解题思路分析

这道题其实是两个小问题的组合，我们可以分开来思考，就像猫猫先玩毛线球再追小蝴蝶一样，一件一件来，呐！

问题二：最长“相等”子序列

我们先来解决比较简单的那个——子序列问题！

子序列的特点是我们可以不连续地从原字符串中挑选字符。要组成一个 '0' 和 '1' 数量相等的子序列，假设我们用了 k 个 '0' 和 k 个 '1'，那么子序列的总长度就是 $2k$ 。为了让长度最大，我们当然希望 k 越大越好啦！

那 k 最大能是多少呢？这取决于原字符串 T 中 '0' 和 '1' 的数量，对吧？假设 T 中总共有 count0 个 '0' 和 count1 个 '1'。我们最多能拿出 count0 个 '0' 和 count1 个 '1'。所以，能组成的对数 k，最大值就是它们中较少的那个，也就是 $k = \min(count0, count1)$ 。

所以，最长“相等”子序列的长度就是 $2 \times \min(count0, count1)$ 。我们只需要数一下整个字符串里 '0' 和 '1' 的个数就可以啦，是不是很简单呀，喵~

问题一：最长“相等”子串

接下来是稍微有点挑战的子串问题。子串必须是连续的，这让问题变得有趣起来了。

如果我们暴力枚举所有的子串，再逐个计算 '0' 和 '1' 的数量，时间复杂度会是 $O(N^2)$ 或者 $O(N^3)$ ，对于比较大的字符串长度 N 来说，肯定会超时的说。我们需要一个更聪明的办法！

这种涉及“子数组/子串和”或“计数”的问题，有一个非常经典的技巧——前缀和 (Prefix Sum) + 哈希表 (Hash Table)！

问题的转换 我们想找一个子串，其中 count('0') == count('1')。这等价于 count('0') - count('1') == 0。为了利用这个关系，我们可以把字符串转换成数字序列。一个绝妙的想法是：把 '0' 当作 +1，'1' 当作 -1（反过来也可以，效果是一样的）。这样一来，原先的条件 count('0') == count('1') 就变成了一个更漂亮的数学形式：子串中所有数字的和为 0！
前缀和登场 现在问题变成了：找到一个最长的子串，其元素和为 0。对于一个数组，如何快速计算任意子数组 [i, j] 的和呢？对啦，就是前缀和！我们创建一个前缀和数组 prefixSum，其中 prefixSum[k] 表示从字符串开头到第 k 个位置的累计和。那么，子串 [i, j] 的和就可以表示为 prefixSum[j] - prefixSum[i-1]。我们想让这个和为 0，也就是 prefixSum[j] - prefixSum[i-1] = 0，即 prefixSum[j] == prefixSum[i-1]。
哈希表加速 我们的目标是找到两个下标 p 和 q（这里 p = i-1, q = j），使得 prefixSum[p] == prefixSum[q]，并且它们的距离 q - p 最大。
这要怎么找呢？我们可以一边计算前缀和，一边用一个哈希表（在 C++ 中是 std::unordered_map）来记录每个前缀和值第一次出现的位置。
让我们来模拟一下这个过程：
- 我们从左到右遍历字符串，计算当前的前缀和 currentSum。
- 在遍历到位置 i 时，我们检查 currentSum 是否已经在哈希表中出现过。
  - 如果出现过，假设它第一次出现在位置 j。这意味着从 j+1 到 i 的这个子串，它的和恰好是 0！它的长度就是 i - j。我们就用这个长度来更新我们的最大长度记录。
  - 如果没出现过，说明这是 currentSum 这个值第一次露面，我们就把它的当前位置 i 记录到哈希表中：map[currentSum] = i。
为了处理好边界情况（比如从头开始的子串），我们可以在开始前，就在哈希表中记下 map[0] = -1。这样，如果从位置 0到 i 的子串和恰好是 0，我们就能计算出长度 i - (-1) = i + 1，正好是子串的长度，完美！
通过这种方式，我们只需要遍历一次字符串，就能找到答案了，时间复杂度是美妙的 $O(N)$ ，喵~

代码实现

这是我根据上面的思路，精心为你准备的一份代码哦！注释写得很详细，希望能帮助你理解呐~

cpp

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

// 一个乐于助人的函数，用来求两个数的最小值，喵~
int min(int a, int b) {
    return a < b ? a : b;
}

// 另一个乐于助人的函数，求最大值！
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    // 使用 std::ios::sync_with_stdio(false) 和 cin.tie(nullptr) 可以让输入输出更快哦！
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // --- Part 1: 最长“相等”子串 (Prefix Sum + Hash Map) ---
    int maxSubstringLength = 0;
    // 哈希表，记录每个前缀和第一次出现的位置
    // key: 前缀和的值
    // value: 第一次出现该前缀和时的下标
    std::unordered_map<int, int> firstOccurrence;
    
    // 初始化：前缀和为0在-1位置出现过，处理从头开始的子串
    firstOccurrence[0] = -1;
    
    int prefixSum = 0;
    int countOfZeros = 0; // 顺便为Part 2统计0的数量

    for (int i = 0; i < n; ++i) {
        // 更新前缀和：将'0'视为+1，'1'视为-1
        if (s[i] == '0') {
            prefixSum += 1;
            countOfZeros++;
        } else {
            prefixSum -= 1;
        }

        // 检查当前前缀和是否已经出现过
        if (firstOccurrence.count(prefixSum)) {
            // 如果出现过，说明从 firstOccurrence[prefixSum] + 1 到 i 的子串和为0
            // 计算这个子串的长度，并更新最大长度
            int currentLength = i - firstOccurrence[prefixSum];
            maxSubstringLength = max(maxSubstringLength, currentLength);
        } else {
            // 如果是第一次遇到这个前缀和，记录下它的位置
            firstOccurrence[prefixSum] = i;
        }
    }

    // --- Part 2: 最长“相等”子序列 ---
    int countOfOnes = n - countOfZeros;
    int maxSubsequenceLength = 2 * min(countOfZeros, countOfOnes);

    // 输出两个答案，中间用空格隔开
    std::cout << maxSubstringLength << " " << maxSubsequenceLength << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们只对长度为 $N$ 的字符串进行了一次完整的遍历。在循环中，对哈希表 std::unordered_map 的操作（插入和查找）平均时间复杂度是 $O(1)$ 。所以总的时间复杂度是线性的，也就是 $O(N)$ 。这对于处理大规模数据来说非常高效，喵~
空间复杂度: $O(N)$ 我们使用了一个哈希表 firstOccurrence 来存储前缀和及其首次出现的位置。在最坏的情况下（例如字符串 "000..." 或 "010101..."），前缀和的值可能都是独一无二的，哈希表的大小会增长到与字符串长度 $N$ 相当。所以，额外空间复杂度是 $O(N)$ 。

知识点总结

这道题真是太棒了，让我们温习了几个重要的知识点呢！

问题分解: 将一个复杂问题拆解成几个更简单的子问题（子串问题和子序列问题），是解决算法题的一个通用策略。
子串 vs 子序列: 深刻理解两者的区别。子串问题通常与连续性有关，常使用滑动窗口、前缀和等技巧。子序列问题则更灵活，往往可以通过计数、动态规划或贪心来解决。
前缀和 + 哈希表: 这是一个黄金组合！当你需要寻找一个子数组/子串满足某种“和”或“计数差”的条件时（比如和为 k，或两种元素数量相等），一定要先想想这个模式。
巧妙转换: 将字符 '0' 和 '1' 转换为数值 +1 和 -1 是解题的关键一步。这种转换将一个计数问题转化为了一个代数求和问题，让前缀和的应用变得顺理成章。

希望这篇题解能帮到你哦！继续加油，你超棒的！喵~ >ω<

Crazy Binary String - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

问题二：最长“相等”子序列 ​

问题一：最长“相等”子串 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​