Submission #2517088

---

Source Code Expand

#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int DP[210000] = {};
int m[(1 << 26)] = {};

//map<int, int> m;
//map<int, int>::iterator ite;

int main(){
	
	string str;
	cin >> str;
	
	int num = 0;
	DP[0] = 0;
	m[0] = 1;
	for(int i = 0; i < str.size(); i++){
		DP[i + 1] = 10000000;
		num = (num ^ (1 << (str[i] - 'a')));
		//ite = m.find(num);
		if(m[num] == 0){
			m[num] = i + 2;
		}else{
			DP[i + 1] = min(DP[i + 1], DP[m[num] - 1] + 1);
		}
		for(int j = 0; j < 26; j++){
			int state = (num ^ (1 << j));
			if(m[state] != 0){
				DP[i + 1] = min(DP[i + 1], DP[m[state] - 1] + 1);
			}
		}
	}
	
	for(int i = 0; i <= str.size(); i++){
		//cout << DP[i] << " ";
	}
	
	cout << DP[str.size()] << endl;
	
	return 0;
}

Submission Info

Judge Result