T2最长的AB序列(20分) - 京东前端笔试编程题&题解

考试平台： 牛客网

题目类型： 选择题（40分） + 3道编程题（60分）

考试时间： 2024-03-23 （两小时）

题目描述

给出一个仅由字符AB构成的字符串Str

请你求出S中包含A和B个数相同的连续区间的最长长度。

输入描述

输入的第一行给出字符串S。（）

输出描述

输出S中包含A和B个数相同的连续区间的最长长度。

示例1

输入：
AAAAAA

输出：
0

示例2

输入：
AAABBBBAAABBB

输出：
12

题解

这道题目属于字符串和前缀和类型的算法题。需要统计字符串中包含A和B个数相同的连续区间的最长长度。

解题思路：

1. 首先读取输入的字符串S。
2. 将字符串S中的字符'A'视为1，字符'B'视为-1，并计算前缀和数组pre_sum，表示从字符串开始到当前位置的A和B的数量差值。
3. 遍历前缀和数组pre_sum，使用哈希表min_pos记录每个差值首次出现的位置，同时更新最长长度max_length，即当前位置与首次出现位置之间的距离。

s = input()
n = len(s)

# 当字符串为 A 看做 1， 否则看成 -1 , 然后对数字进行求前缀和
pre_sum = [0] * (n + 1)
for i in range(n):
    pre_sum[i + 1] = pre_sum[i] + 1 if s