解题思路

关键观察

• 只关心奇偶性（每种字母出现次数 mod 2）。
• 令 mask[i] 表示前缀 s[1..i] 的 26 位奇偶掩码（第 $k$ 位为该字母出现次数的奇偶）。
• 子串 s[l..i] 的掩码为 mask[l-1] ^ mask[i]。
• 若该子串“无害”，则 popcount(mask[l-1] ^ mask[i]) ∈ {0,1}（全 0 或恰好一个 1）。

状态设计

设 dp[i] = 把前缀 s[1..i] 切成“无害”若干段的最少段数。 答案为 dp[n]，dp[0]=0。

同时维护数组 best[mask]：到目前为止前缀掩码为 mask 时的最小 dp 值。

• 初始 best[0]=0（空前缀），其余为 $+\infty$。

转移

处理到位置 i 时已知 mask[i]。最后一段从某个 j+1 切到 i：

• 若 mask[j] == mask[i]（该段掩码为 0），候选值 best[mask[i]] + 1。
• 若 mask[j] == mask[i] ^ (1<<k)（该段掩码只有一位为 1），候选值 best[mask[i] ^ (1<<k)] + 1，遍历 $k=0..25$。

因此

dp[i] = 1 + min( best[mask[i]],
                 min_{k=0..25} best[mask[i] ^ (1<<k)] )

随后用 dp[i] 更新 best[mask[i]] = min(best[mask[i]], dp[i])。

实现细节

• 字母表固定 26，故 mask 用 32 位整型即可。
• 只需线性扫描一次，外层 $n$，内层常数 26，整体 $O(n·26)$。
• 空间：best 大小为 $2^{26}$ 看似巨大，但我们只访问到出现过的掩码。实现中用哈希表（Python dict/C++ unordered_map/Java HashMap）存储 best，初始放入 (0 -> 0) 即可。

复杂度

• 时间复杂度：$O(n \times 26)$。
• 空间复杂度：平均 $O(U)$，其中 $U$ 为出现过的不同前缀掩码个数（$\le n+1$）。

代码

Python

# 读取输入，计算最少段数
import sys

s = sys.stdin.readline().strip()
n = len(s)

# best[mask] = 前缀掩码为 mask 的最小 dp 值
best = {0: 0}
dp = [0] * (n + 1)

mask = 0
for i, ch in enumerate(s, 1):
    # 更新当前位置前缀掩码（翻转对应字母的奇偶位）
    mask ^= 1 << (ord(ch) - 97)

    # 计算 dp[i]
    ans = best.get(mask, 10**9)  # 子串掩码为 0 的情况
    # 子串掩码只有一位为 1 的情况
    for k in range(26):
        ans = min(ans, best.get(mask ^ (1 << k), 10**9))
    dp[i] = ans + 1

    # 用 dp[i] 更新 best
    if dp[i] < best.get(mask, 10**9):
        best[mask] = dp[i]

print(dp[n])

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int n = s.length();

        // best: 掩码 -> 最小 dp
        HashMap<Integer, Integer> best = new HashMap<>();
        best.put(0, 0); // 空前缀

        int[] dp = new int[n + 1];
        int mask = 0;

        for (int i = 1; i <= n; i++) {
            // 更新掩码：翻转当前字母位
            int c = s.charAt(i - 1) - 'a';
            mask ^= (1 << c);

            // 候选 1：子串掩码为 0
            int INF = 1_000_000_000;
            int cur = best.getOrDefault(mask, INF);

            // 候选 2：子串掩码仅 1 位为 1
            for (int k = 0; k < 26; k++) {
                int t = mask ^ (1 << k);
                cur = Math.min(cur, best.getOrDefault(t, INF));
            }
            dp[i] = cur + 1;

            // 更新 best
            best.put(mask, Math.min(best.getOrDefault(mask, INF), dp[i]));
        }

        System.out.println(dp[n]);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (!getline(cin, s)) return 0;
    int n = (int)s.size();

    unordered_map<int,int> best;
    best.reserve(n * 2 + 5);
    best[0] = 0; // 空前缀

    const int INF = 1e9;
    vector<int> dp(n + 1, 0);

    int mask = 0;
    for (int i = 1; i <= n; ++i) {
        // 翻转当前字母位
        mask ^= 1 << (s[i-1] - 'a');

        // 候选：掩码为 0
        int cur = best.count(mask) ? best[mask] : INF;

        // 候选：掩码仅 1 位为 1
        for (int k = 0; k < 26; ++k) {
            int t = mask ^ (1 << k);
            auto it = best.find(t);
            if (it != best.end()) cur = min(cur, it->second);
        }
        dp[i] = cur + 1;

        // 更新 best
        auto it = best.find(mask);
        if (it == best.end()) best[mask] = dp[i];
        else it->second = min(it->second, dp[i]);
    }

    cout << dp[n] << "\n";
    return 0;
}

题目内容

小明是一个魔法项链回收商，他的工作是将这些魔法项链进行无害化处理，魔法项链由若干颗魔法石组成，可以视作一个字符串，不同种类的魔法石可以用小写字母 $a$ ~ $z$ 来进行表示。小明可以将魔法项链切割为若于段(也可以不切割)，每一段中相同种类的魔法石可以进行能量抵消，如果最终宝石全部抵消或者只剩一颗，那么就算完成了无害化处理。

例如：

项链段 $zz$ 可以完成无害化。

项链段 $aba$ 可以完成无害化，$aa$ 可以抵消，最后只一颗 $b$ ；

项链段 $cccg$ 不可以完成，因为 $cc$ 抵消后还剩下 $cg$ ，不止一颗。

今天小明又回收到了一条魔法项链，他想知道最少需要将魔法项链切割成多少子段，可以使所有子段都可以完成无害化处理。

输入描述

一个字符串，只包含小写字母，用来表示小明回收的魔法项链，长度不超过 $100000$

输出描述

一个整数，表示最小需要切割为多少段，可以使所有项链子段都能完成无害化处理。

样例1

输入

xyz

输出

3

样例2

输入

abcdabcd

输出

1

说明

无需切割，最初的项链串本身就可以完成无害化处理，此时记为 $1$ 段。

样例3

输入

rrzbbaau

输出

2

说明

可以切割为 $rrz,bbaau$ 两个子串。