JOIOJI

wjh15101051's space

卧薪尝胆，厚积薄发。

JOIOJI

Date: Fri Sep 14 08:08:42 CST 2018

In Category: NoCategory

Description：

给一个只包含三个字母的字符串，找一个最长的包含全部三个字母数量相等的子串。

$1\le n \le 200000$

Solution：

如果只有两个字母的话肯定是统计两种个数的前缀和做差放到 $map$ 里，每次查询最早加入的，如果有三个，那就两两做差即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

inline char getc()

{

	register char c = getchar();

	while(c != 'J' && c != 'O' && c != 'I')c = getchar();

	return c;

}

map<pair<int,int>,int> p;

map<char,int> cnt;

int main()

{

	scanf("%d",&n);

	char c;

	int ans = 0;

	p[make_pair(0,0)] = 0;

	for(int i = 1;i <= n;++i)

	{

		c = getc();

		++cnt[c];

		pair<int,int> res = make_pair(cnt['J'] - cnt['O'],cnt['O'] - cnt['I']);

		if(p.find(res) != p.end())ans = max(ans,i - p[res]);

		else p[res] = i;

	}

	cout << ans << endl;

	return 0;

}

In tag: 玄学

wjh15101051