最长的AB序列
[题目链接](https://www.nowcoder.com/practice/d3c73cbd06ef491bbb50bd7fc51d84c7)
思路
题目要求:给一个只含 A 和 B 的字符串,找出最长的连续子串,使得其中 A 和 B 的个数相同。
先想一个暴力做法——枚举所有子串,统计 A、B 个数,取满足条件的最长长度。但这样是 的,数据量大了扛不住。
换个角度想:如果我们把 A 看作 +1,B 看作 -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();
});
复杂度分析
- 时间复杂度:
,其中
是字符串长度。只需遍历一次字符串,哈希表的查询和插入均为
。
- 空间复杂度:
,哈希表最多存储
个不同的前缀和值。

京公网安备 11010502036488号