2017 360春招在线笔试题 偶串

题目: 一个字符串,如果其中每个不同的字符个数均为偶数, 该串为偶串,比如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;
}