题面描述:

塔子哥最近迷上了一个字符串重排的游戏。游戏规则是给定一个由小写字母组成的字符串 ( s )，通过重新排列 ( s ) 中的字母，看看最多能组成多少个不同的回文字符串。如果无法组成任何回文字符串，则输出 ( 0 )。请编写一个程序来实现这个功能。输入格式为一行包含字符串 ( s )，输出格式为一个整数，表示可以组成的不同回文字符串的数量。例如，输入 "aabb" 时，输出应为 ( 2 )。

思路

如果存在两个以上的个数为奇数的字符显然不能构成回文。

对于其他为偶数的情况，因为是回文串，所以我们只需考虑其中半边的情况即可。

现在问题变成了，有 K 种字母，每个字母的个数为 $cnt_i$ 个，问有多少种情况

假设 K 种字母的和为 $n$

那么计算公式为：

对此我们只需预处理阶层即可 $O(1)$ 计算单个结果，由于涉及到大数运算，这里采用 python 来实现。

关键点分析

1. 回文字符串的特性：

   • 对于一个字符串能构成回文，最多只能有一个字符出现奇数次。因为在回文的中心可以放置这个字符，而其他字符必须成对出现。
   • 如果存在两个或以上的字符出现奇数次，则无法构成回文串，直接输出 ( 0 )。

2. 字符计数：

   • 统计字符串中每个字符的出现次数，分为奇数和偶数。
   • 只需要考虑每个字符的一半的数量来计算不同的回文串，因为回文的前半部分决定了整个回文。

3. 排列计算：

   • 计算回文的一半所需的字符的排列方式。假设我们有 ( K ) 种字符，每种字符的数量为 ( cnt_i )，我们需要计算总的排列数。
   • 总的排列数为所有字符的一半的总数的阶乘，然后除以每种字符的一半的数量的阶乘，以避免重复排列。

解决方案步骤

1. 统计字符频率：使用哈希表统计每个字符的出现次数。
2. 判断奇数字符的数量：遍历统计结果，记录出现奇数次的字符数量。
   • 如果奇数字符的数量大于 1，则输出 ( 0 )。
3. 计算字符的半数：将每个字符的计数除以 2，存储这些值。
4. 预处理阶乘：计算并存储从 ( 0 ) 到 ( n ) 的阶乘，以便后续快速计算。
5. 计算回文串的数量：根据公式计算可能的排列数，输出结果。

AC代码

Python

from collections import Counter


s = input().strip()
mp = Counter(s)  # 统计字符串中各个字符的个数
cnt = 0
v = []

# 统计奇数字符个数和偶数字符个数
for value in mp.values():
    if value % 2 == 1:
        cnt += 1
    v.append(value // 2)

# 如果奇数字符个数大于1，则无法构成回文串
if cnt > 1:
    print(0)
    exit(0)

# 计算回文串数量
total = sum(v)  # 总的字符数量的一半
f = [1] * (total + 1)  # 预处理阶乘值
for i in range(1, total + 1):
    f[i] = f[i - 1] * i

res = f[total]  # 计算全部字符的排列数
for i in v:
    res //= f[i]  # 除去各个字符的排列数

print(res)

java

import java.math.BigInteger;
import java.util.*;

public class Main {
    private static BigInteger palindromeNum(String str) {
        // 将字符串转换为字符数组
        char[] s = str.toCharArray();
        // 创建一个长度为26的数组，存储每个字母出现的次数
        int[] map = new int[26];
        for (char c : s) {
            map[c - 'a']++;
        }
        // 判断是否有超过一个的奇数字符
        boolean odd = false;
        for (int i = 0; i < 26; i++) {
            if (map[i] % 2 == 1) {
                if (odd) {
                    // 如果有超过一个奇数字符，则无法构成回文串，返回0
                    return new BigInteger("0");
                } else {
                    odd = true;
                }
            }
            // 将每个字母的个数除以2，因为回文串中每个字母出现的次数必须是偶数
            map[i] /= 2;
        }
        // 计算回文串的数量
        int n = s.length / 2;
        // 预先计算阶乘值，以便后续使用
        BigInteger[] f = new BigInteger[n + 1];
        f[0] = new BigInteger("1");
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1].multiply(new BigInteger(String.valueOf(i)));
        }
        // 除去每种字符的排列数
        for (int i = 0; i < 26; i++) {
            if (map[i] > 0) {
                f[n] = f[n].divide(f[map[i]]);
            }
        }
        return f[n];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        System.out.println(palindromeNum(s));
    }
}

C++

塔子哥的tips:这题确实对C++不公平。同样的思路却需要自己实现大整数，而其他语言都有对大整数模拟的封装。但是也没办法，因为C++实现大整数需要100+行代码。如果真的追求完美，C++这题起码写200行。所以碰到这种出题人，只能认栽。写个正常的算法看看能过多少就算了。赶快去其他题拿分。

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;

    // 统计字符串中各个字符的个数
    unordered_map<char, int> mp;
    for (char c : s) {
        mp[c]++;
    }

    int cnt = 0;
    vector<int> v;

    // 统计奇数字符个数和偶数字符个数
    for (auto [_, value] : mp) {
        if (value % 2 == 1) {
            cnt++;
        }
        v.push_back(value / 2);
    }

    // 如果奇数字符个数大于1，则无法构成回文串
    if (cnt > 1) {
        cout << 0 << endl;
        return 0;
    }

    // 计算回文串数量
    int total = 0;
    for (int x : v) {
        total += x;
    }

    vector<long long> f(total + 1, 1);  // 预处理阶乘值
    for (int i = 1; i <= total; i++) {
        f[i] = f[i - 1] * i;
    }

    long long res = f[total];  // 计算全部字符的排列数
    for (int x : v) {
        res /= f[x];  // 除去各个字符的排列数
    }

    cout << res << endl;
    return 0;
}

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 计算回文排列数量
function palindromeNum(str) {
    let s = str.split("");
    let map = Array(26).fill(0);

    for (let c of s) {
        map[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    let odd = false;
    for (let i = 0; i < 26; i++) {
        if (map[i] % 2 === 1) {
            if (odd) return BigInt(0); // 超过一个奇数字符，无法构成回文
            odd = true;
        }
        map[i] = Math.floor(map[i] / 2);
    }

    let n = Math.floor(s.length / 2);
    let f = Array(n + 1).fill(BigInt(1));

    for (let i = 1; i <= n; i++) {
        f[i] = f[i - 1] * BigInt(i);
    }

    let result = f[n];
    for (let i = 0; i < 26; i++) {
        if (map[i] > 0) {
            result /= f[map[i]];
        }
    }

    return result;
}

// 处理输入
(async function () {
    let s = await readline();
    console.log(palindromeNum(s).toString()); // 输出结果
    rl.close();
})();

问题描述

小明最近迷上了一个字符串重排的游戏。游戏规则如下:给定一个由小写字母组成的字符串 $s$,通过重新排列 $s$ 中的字母,看看最多能组成多少个不同的回文字符串。回文字符串是指一个字符串正着读和反着读完全一样,例如"level"和"noon"都是回文字符串,而"code"不是。

请你帮小明写一个程序,计算给定字符串 $s$ 经过重排后最多能组成的不同回文字符串数量。

输入格式

输入一行,包含一个由小写字母组成的字符串 $s$,表示小明手中的初始字符串。

输出格式

输出一个整数,表示字符串 $s$ 经过重排后最多能组成的不同回文字符串数量。如果无法组成任何回文字符串,则输出 $0$。

样例输入

aabb

样例输出

2

评测数据与规模

• $1 \leq |s| \leq 1000$
• 字符串 $s$ 只包含小写字母