題目: 一個字符串,如果其中每個不同的字符個數均為偶數, 該串為偶串,比如abab, 有兩個a和兩個b. 但 abb就不是,因為只有一個a. 現在給定字符串s, 求其子串是偶串的個數. 子串不包括空串.
輸入: 字符串s
輸出: 子串為偶串個數
例
輸入: abbcc
輸出: 3
因為子串為偶串的子串有: bb, cc, bbcc
解題關鍵思路: 偶數個字符c異或為0.
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main() {
string s;
cin>> s;
map<int, int> m;
m[0] = 1;
int t = 0;
for (int i = 0; i < s.size(); ++i) {
t ^= (1<<(s[i] - 'a'));
m[t] += 1;
}
int ans = 0;
map<int, int>::iterator iter;
for (iter = m.begin(); iter != m.end(); ++iter) {
ans += iter->second * (iter->second - 1) / 2;
}
cout<<ans<<endl;
return 0;
}
