最长的AB序列

[题目链接](https://www.nowcoder.com/practice/d3c73cbd06ef491bbb50bd7fc51d84c7)

思路

题目要求:给一个只含 AB 的字符串,找出最长的连续子串,使得其中 AB 的个数相同。

先想一个暴力做法——枚举所有子串,统计 A、B 个数,取满足条件的最长长度。但这样是 的,数据量大了扛不住。

换个角度想:如果我们把 A 看作 +1B 看作 -1,那么"A 和 B 个数相同"就等价于"子串的和为 0"。这就转化成了一个经典问题——最长的和为 0 的子数组

怎么求呢?用前缀和 + 哈希表

表示前 个字符的前缀和。如果 ),说明从 这段子串的和为 0,长度为

所以我们只需要用哈希表记录每个前缀和第一次出现的位置。遍历字符串时,如果当前前缀和已经在哈希表中出现过,就用当前位置减去第一次出现的位置来更新答案;否则就把当前前缀和和位置存入哈希表。

别忘了初始化:前缀和为 0 对应的位置是 (代表还没开始遍历的时候),这样如果整个前缀本身和为 0,也能正确计算长度。

拿样例验证一下:AAABBBBAAABBB,前缀和依次是 1,2,3,2,1,0,-1,0,1,2,1,0,-1。前缀和 0 第一次在位置 出现,最后一次在位置 11 出现,长度 ,正确。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    unordered_map<int, int> first;
    first[0] = -1;
    int prefix = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        prefix += (s[i] == 'A') ? 1 : -1;
        if (first.count(prefix)) {
            ans = max(ans, i - first[prefix]);
        } else {
            first[prefix] = i;
        }
    }
    cout << ans << endl;
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int prefix = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            prefix += (s.charAt(i) == 'A') ? 1 : -1;
            if (first.containsKey(prefix)) {
                ans = Math.max(ans, i - first.get(prefix));
            } else {
                first.put(prefix, i);
            }
        }
        System.out.println(ans);
    }
}
def main():
    s = input().strip()
    first = {0: -1}
    prefix = 0
    ans = 0
    for i, c in enumerate(s):
        prefix += 1 if c == 'A' else -1
        if prefix in first:
            ans = max(ans, i - first[prefix])
        else:
            first[prefix] = i
    print(ans)

main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', (line) => {
    const s = line.trim();
    const first = new Map();
    first.set(0, -1);
    let prefix = 0, ans = 0;
    for (let i = 0; i < s.length; i++) {
        prefix += s[i] === 'A' ? 1 : -1;
        if (first.has(prefix)) {
            ans = Math.max(ans, i - first.get(prefix));
        } else {
            first.set(prefix, i);
        }
    }
    console.log(ans);
    rl.close();
});

复杂度分析

  • 时间复杂度,其中 是字符串长度。只需遍历一次字符串,哈希表的查询和插入均为
  • 空间复杂度,哈希表最多存储 个不同的前缀和值。