Crazy Binary String

登录—专业IT笔试面试备考平台_牛客网

题目大意：有一个长度为n的由0,1组成的字符串，问串内0,1数量相同的最长子串和最长子序列的长度

1<=n<=1e5

思路：求最长子序列的长度只需统计字符串内1的数量和0的数量，求最小值，对于最长子串，我们遍历字符串，维护一个前缀和sum,遇到0，sum-1,遇到1，sum+1，记录每个sum第一次出现的位置，如果后面遇到相同的，就说明从之前的位置到这都是合法的，就记录当前位置和之前记录的位置的差，记录最大值，如果当前的sum=0了，说明从头到这都是合法的直接将答案置为当前位置

#include
#include
using namespace std;
const int N = 1e5 + 5;
int pos[N];
int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	int len = s.length();
	int sum = 0, ans = 0;;
	int cnt1 = 0, cnt0 = 0;
	for (int i = 0; i < len; i++)
	{
		if (s[i] == '0')
		{
			sum--;//遇到0，前缀和-1,
			cnt0++;//统计0的个数
		}
		else
		{
			sum++;//遇到1，前缀和+1
			cnt1++;//统计1的个数
		}
		if (pos[sum] == 0)
		{
			pos[sum] = i;//记录第一次出现这个前缀和的位置
		}
		else
		{
			ans = max(ans, i - pos[sum]);//不是第一次出现的话，记录当前位置到第一次位置之间的长度
		}
		if (sum == 0)
		{
			ans = i+1;//从头到当前位置都是合法的
		}
	}
	printf("%d %d", ans, min(cnt1, cnt0)<<1);
	return 0;
}