【题目来源】
蓝桥云课：1.小郑的蓝桥平衡串 - 蓝桥云课 (lanqiao.cn)
【题目描述】
平衡串指的是一个字符串，其中包含两种不同字符，并且这两种字符的数量相等。
例如， ababab和aababb都是平衡串， 因为每种字符各有三个， 而abaab和aaaab都不是平衡串，因为它们的字符数量不相等。
平衡串在密码学和计算机科学中具有重要应用，比如可以用于构造哈希函数或者解决一些数学问题。
小郑拿到一个只包含L、Q的字符串，他的任务就是找到最长平衡串，且满足平衡串的要求，即保证子串中L、Q的数量相等。
【输入】
输入一行字符串，保证字符串中只包含字符L、Q.
【输出】
输出一个整数，为输入字符串中最长平衡串的长度。
【输入样例】
LQLL
【输出样例】
2
【算法标签】
《蓝桥云课 3419 小郑的蓝桥平衡串》 #字符串# #前缀和#
【代码详解】
from itertools import accumulateMOD = 1000000007 # 定义模数def get_presum(a):"""计算数组a的前缀和并取模参数:a: 输入数组返回:前缀和数组，每个元素对MOD取模"""sum = list(accumulate(a)) # 使用itertools.accumulate计算前缀和sum = [x % MOD for x in sum] # 对每个前缀和取模return sumdef get_sum(sum, l, r):"""快速计算区间和[l,r]参数:sum: 前缀和数组l: 区间左端点r: 区间右端点返回:区间和，结果对MOD取模"""if l == 0:return sum[r] # 如果从0开始，直接返回sum[r]else:# 否则返回sum[r] - sum[l-1]，并处理负数情况return (sum[r] - sum[l-1] + MOD) % MODS = input() # 输入字符串
n = len(S) # 字符串长度
a = [] # 数值化后的数组# 将字符串转换为数值数组
for x in S:if x == 'L':a.append(1) # 'L'对应1else:a.append(-1) # 'R'对应-1sum = get_presum(a) # 计算前缀和
ans = 0 # 初始化最长平衡子串长度# 双重循环检查所有可能的子串
for l in range(n): # 左端点for r in range(l, n): # 右端点# 如果区间和为0，说明L和R数量相等if get_sum(sum, l, r) == 0:# 更新最大长度ans = max(ans, r - l + 1)print(ans) # 输出结果
【运行结果】
LQLL
2