问题描述
平衡串指的是一个字符串，其中包含两种不同字符，并且这两种字符的数量相等。
例如，abababababab 和 aababbaababb 都是平衡串，因为每种字符各有三个，而 abaababaab 和 aaaabaaaab 都不是平衡串，因为它们的字符数量不相等。
平衡串在密码学和计算机科学中具有重要应用，比如可以用于构造哈希函数或者解决一些数学问题。
小郑拿到一个只包含 L、Q 的字符串，他的任务就是找到最长平衡串，且满足平衡串的要求，即保证子串中 L、Q 的数量相等。
输入格式
输入一行字符串，保证字符串中只包含字符 L、Q。
输出格式
输出一个整数，为输入字符串中最长平衡串的长度。
样例输入
LQLL
样例输出
2
解题思路
1. 字符映射：L看成+1，Q看成-1。
如果一段区间内 L 和 Q 数量相等，这段区间所有数字加起来总和 = 0。
2. 前缀和结论：
区间 [l+1, r] 和 = sum[r] - sum[l]
和为0等价于： sum[r] == sum[l]
两个位置前缀和相等，中间这一段就是平衡串
3. 数组 bj[] 充当记录本：保存这个sum值第一次出现的标记位置。只存第一次，后面再次碰到相同sum，算出来的长度才是最大。
4. +1000：sum会出现负数，C语言不允许负下标，sum+1000平移到0~2000。
5. 循环写法（i从0开始，直接访问 s[i] ，不用i-1，不容易写错）
注意： i 是字符串下标，读完 s[i] 对应的前缀和标记位置是 i+1 (变成长度位置)
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int bj[2007];
int main(int argc, char *argv[])
{
int i;
for(i=0;i<=2007;i++)
{
bj[i]=-1;
}
char s[1000];
scanf("%s",s);
int n=strlen(s);
int sum=0;
int maxlen=0;
for(i=0;i<n;i++)
{
int L=0,Q=0;
if(s[i]=='L')
{
sum++;
}
else
{
sum--;
}
int pos=sum+1000;
if(bj[pos]!=-1)
{
int len=(i+1)-bj[pos];
if(len>maxlen)
{
maxlen=len;
}
}
else
{
bj[pos]=i+1;
}
}
printf("%d\n",maxlen);
return 0;
}
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2402_87421821/article/details/170448283
