Submission #1799551

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
#define BUF (100005)
#define ll long long 

char s[BUF];
int  a[BUF];
int  d[BUF];
vector<int> h[1<<26];

int main(void){
	cin >> s;
	int n=strlen(s);

	int bit = 0;;
	for(int i=0;i<n;i++){
		a[i]=bit;
		h[bit].push_back(i);
		int tmp=s[i]-'a';		
		bit ^=1<<tmp;
	}
	a[n]=bit;
	h[bit].push_back(n);

	d[0] = 0;
	d[1] = 1;

	for(int i=1;i<n;i++){
		int min = -1;

		for(int j=0;j<=26;j++){
			int tmp=1<<j;
			tmp=a[i+1]^tmp;
			if(j==26) tmp=a[i+1];
			for(auto x:h[tmp]){
				int k;
				if(x<=i){
	//				cout << i << " " << x << "\n";
					k=d[x]+1;
				}
				if(min==-1 || min>k) min=k;
			}
		}
		d[i+1]=min;
	//	printf("d[%d]=%d\n",i+1,min);
	}

	cout << d[n] << endl;
	return 0;
}

Submission Info

Judge Result