题目链接

最长的AB序列

题目描述

给出一个仅由字符 'A' 和 'B' 构成的字符串，请你求出其中包含 'A' 和 'B' 个数相同的最长连续区间的长度。

解题思路

这是一个求解特定条件的子数组问题。直接暴力枚举所有子数组并计数，时间复杂度会达到 ，对于较大的字符串会超时。我们可以通过一个巧妙的转换，使用前缀和与哈希表在 的时间内解决。

1. 问题转换

核心条件是“'A' 和 'B' 个数相同”。我们可以将这个问题转化为一个求和问题：

  • 将字符 'A' 视为数值 +1。
  • 将字符 'B' 视为数值 -1。

经过这个转换，一个连续区间中 'A' 和 'B' 的数量相等，就等价于这个区间内所有数值的总和为 0。

2. 前缀和与哈希表

现在问题变成了：找到和为 0 的最长连续子数组。这是一个经典的前缀和问题。

  • 我们定义 prefix_sum[i] 为字符串前 i 个字符对应的数值之和。
  • 如果子数组 s[i...j] 的和为 0，那么 prefix_sum[j+1] - prefix_sum[i] 必定为 0，也就是说 prefix_sum[j+1] == prefix_sum[i]。
  • 我们的目标就是找到相等的两个前缀和，并使它们的索引差最大。

为了高效地实现这一点，我们使用一个哈希表（Map）来存储每个前缀和第一次出现的位置。

  • 算法流程：
    1. 初始化最大长度 max_len = 0，当前和 current_sum = 0。
    2. 初始化一个哈希表 first_occurrence，并存入一个初始值 {0: -1}，表示在遍历开始前（索引为-1时），前缀和为0。
    3. 从左到右遍历字符串：

    • 根据当前字符更新 current_sum。

    • 检查 current_sum 是否已在哈希表中。

    • 如果存在： 说明从该前缀和上次出现的位置到现在，中间这段区间的和为0。我们计算其长度 current_index - first_occurrence[current_sum]，并更新 max_len。

    • 如果不存在： 说明这是 current_sum 第一次出现，我们将其存入哈希表 first_occurrence[current_sum] = current_index。我们只记录第一次出现的位置，以保证后续计算出的区间长度是最大的。

    1. 遍历结束后，max_len 即为所求。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    map<int, int> first_occurrence;
    first_occurrence[0] = -1;
    int max_len = 0;
    int current_sum = 0;

    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'A') {
            current_sum++;
        } else {
            current_sum--;
        }

        if (first_occurrence.count(current_sum)) {
            max_len = max(max_len, i - first_occurrence[current_sum]);
        } else {
            first_occurrence[current_sum] = i;
        }
    }

    cout << max_len << endl;

    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        Map<Integer, Integer> firstOccurrence = new HashMap<>();
        firstOccurrence.put(0, -1);
        int maxLen = 0;
        int currentSum = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'A') {
                currentSum++;
            } else {
                currentSum--;
            }

            if (firstOccurrence.containsKey(currentSum)) {
                maxLen = Math.max(maxLen, i - firstOccurrence.get(currentSum));
            } else {
                firstOccurrence.put(currentSum, i);
            }
        }

        System.out.println(maxLen);
    }
}

import sys

def solve():
    s = sys.stdin.readline().strip()
    
    first_occurrence = {0: -1}
    max_len = 0
    current_sum = 0
    
    for i, char in enumerate(s):
        if char == 'A':
            current_sum += 1
        else:
            current_sum -= 1
            
        if current_sum in first_occurrence:
            max_len = max(max_len, i - first_occurrence[current_sum])
        else:
            first_occurrence[current_sum] = i
            
    print(max_len)

solve()

算法及复杂度

  • 算法：前缀和 + 哈希表
  • 时间复杂度：，其中 是字符串的长度。我们只需要对字符串进行一次完整的遍历。
  • 空间复杂度：。在最坏的情况下（例如字符串 AAAA...），每个前缀和都不同，哈希表需要存储 个条目。