思路分析

关键观察

1. 回文的结构 一个回文的字符频率结构：

   • 如果长度是偶数 → 每个字符出现次数均为偶数；
   • 如果长度是奇数 → 恰好有一个字符出现次数为奇数，其他为偶数。

2. 可以任意重排 因为可以任意重排，所以我们只需要根据字符频率来判断最少可以分成多少段。

3. 奇数字符的作用 如果某个字符的出现次数为奇数，那么无论怎么排，它都会导致需要某个回文串的中心有它这个字符。 而一个回文串的中心最多只能接收一个奇数字符，所以：

   • 若有 $k$ 个字符出现次数为奇数，至少需要 $k$ 个回文串。
   • 特例：如果没有字符出现次数为奇数，那么整个字符串可以组成一个回文串，即需要 1 段。

结论公式

设：

那么答案为：

代码实现

C++

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

int main() {
    string s;
    cin >> s;
    vector<int> freq(26, 0);
    // 统计每个字符出现的次数
    for (char c : s) {
        freq[c - 'a']++;
    }
    int odd_count = 0;
    // 统计出现次数为奇数的字符个数
    for (int cnt : freq) {
        if (cnt % 2 == 1) {
            odd_count++;
        }
    }
    // 如果没有奇数字符，则只需1个回文串，否则至少需要odd_count个
    if (odd_count == 0) odd_count = 1;
    cout << odd_count << endl;
    return 0;
}

Python

# 读取输入
s = input().strip()
freq = [0] * 26
# 统计频率
for c in s:
    freq[ord(c) - ord('a')] += 1

# 统计奇数频率的字符数
odd_count = sum(1 for cnt in freq if cnt % 2 == 1)

# 如果没有奇数字符，则答案是1，否则是odd_count
if odd_count == 0:
    odd_count = 1

print(odd_count)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int[] freq = new int[26];
        // 统计字符频率
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        int odd_count = 0;
        // 计算奇数字符的个数
        for (int cnt : freq) {
            if (cnt % 2 == 1) {
                odd_count++;
            }
        }
        // 输出结果
        if (odd_count == 0) odd_count = 1;
        System.out.println(odd_count);
    }
}

题目内容

包包有一个长度为 $n$ 的，仅由小写英文字母构成的字符串 $s$ 。你需要将 $s$ 中的字符任意重排后，划分成若干个连续子串，使得每个字符被恰好一个字串包含，且每个子串都为回文串。请问最少需要划分成多少个连续子串？

【子串】子串为从原字符串中，连续的选择一段字符(可以全选)得到的新字符串。

【回文串】一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

输入描述

输入一行一个仅由小写英文字母构成的字符串 $s(1≦|s|≦ 10^5)$ ，其中 $|s|$ 表示 $s$ 的长度。

输出描述

输出一个整数，表示最少需要划分成多少个连续子串。

样例1

输入

baozii

输出

4

说明

我们可以先将 $baozii$ 重排后变成 $baoizi$ ，然后划分成 $b,a,o,izi$ $4$ 个连续子串，且都为回文串。可以证明，不在一种重排和划分方式使得划分出的子串数量小于 $4$ 。

样例2

输入

zrnstnsr

输出

2