刷题笔记合集🔗

全排列

问题描述

小兰正在学习排列组合的知识。现在她面临一个问题：给定一个只包含大写英文字母的字符串 ，她需要计算出对 重新排列的所有不相同的排列数。

例如： 为 ，则不同的排列有 、、 三种。

输入格式

输入一个长度不超过 的字符串 ，我们确保都是大写的英文字母。

输出格式

输出 重新排列的所有不相同的排列数（包含自己本身）。

样例输入

ABA

ABCDEFGHHA

样例输出

3

907200

样例	解释说明
样例1	的不同排列有 、、 三种。
样例2	共有 种不同的排列。

数据范围

• 字符串 的长度不超过
• 字符串 中的字符均为大写英文字母（）

题解

这道题要求计算一个字符串的所有不同排列的数量，需要考虑字符串中可能存在重复字符的情况。

首先回顾一下排列组合的基础知识：对于一个长度为 n 的字符串，如果所有字符都不同，那么它的排列数量就是 n!（n的阶乘）。但如果字符串中有重复字符，那么排列数量会减少。

对于有重复字符的情况，计算公式如下： 总排列数 = n! / (a! × b! × c! × ...) 其中a, b, c...表示各个字符重复的次数。

例如字符串"ABA"：

• 总字符数n=3
• 字符'A'重复2次，字符'B'重复1次
• 排列数 = 3! / (2! × 1!) = 6 / 2 = 3

具体解题步骤：

1. 计算字符串的总长度n
2. 统计每个字符出现的次数
3. 计算n的阶乘
4. 对于每个重复出现的字符，用其出现次数的阶乘去除总阶乘
5. 得到的结果就是不同排列的数量

时间复杂度分析：

• 统计字符出现次数需要O(n)时间
• 计算阶乘需要O(n)时间
• 总时间复杂度为O(n)

由于题目限制字符串最大长度为10，所以阶乘计算不会溢出整型范围，算法可以高效处理所有测试用例。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def factorial(n):
    """计算阶乘"""
    fact = 1
    for i in range(1, n + 1):
        fact *= i
    return fact

# 读取输入
s = input()

# 计算字符串长度
n = len(s)

# 统计每个字符出现的次数
char_count = {}
for char in s:
    char_count[char] = char_count.get(char, 0) + 1

# 计算总排列数
total = factorial(n)
for count in char_count.values():
    if count > 1:
        total //= factorial(count)

# 输出结果
print(total)

• Cpp

#include <bits/stdc++.h>
using na