统计唯一排列子串的高效方法

本篇文章给大家分享《统计字符串中唯一排列子串数量的高效方法》，覆盖了文章的常见基础知识，其实一个语言的全部知识点一篇文章是不可能说完的，但希望通过这些问题，让读者对自己的掌握程度有一定的认识(B 数)，从而弥补自己的不足，更好的掌握它。

本文讲解如何正确统计目标字符串的所有**不同排列**在源字符串中作为子串出现的次数，重点解决因重复字符导致排列重复计数的问题，并提供简洁、健壮的 Python 实现方案。

在处理字符串排列匹配问题时，一个常见误区是直接使用 itertools.permutations() 生成所有排列后逐个检查——这在目标字符串（needle）含重复字符（如 "aab"）时会产生大量重复排列，导致误计数。例如，permutations('aab') 会生成 6 个元组（因为 3! = 6），但实际不同排列只有 3 个："aab", "aba", "baa"。原始代码将其全部转为列表并遍历，又用变量名 str 覆盖了内置类型，进一步埋下隐患。

正确做法是利用 set 自动去重：set(permutations(N)) 会将相同字符序列的排列合并为唯一项（注意：permutations 返回的是 tuple，如 ('a','a','b')，而 tuple 是可哈希的，因此能被 set 正确去重）。同时，应避免覆盖内置名称，将拼接后的字符串变量命名为 substring 或 pattern 等语义化名称。

以下是优化后的完整实现：

from itertools import permutations

N = input().strip()  # 不需要 str(input())，input() 默认返回字符串
H = input().strip()

# 生成所有不重复的排列（自动去重）
unique_perms = set(permutations(N))
counter = 0

for perm_tuple in unique_perms:
    substring = "".join(perm_tuple)  # 拼接为字符串
    if substring in H:  # Python 的 in 操作符高效判断子串存在性
        counter += 1

print(counter)

更简洁的写法（一行计算）：

from itertools import permutations
N, H = input().strip(), input().strip()
print(sum("".join(p) in H for p in set(permutations(N))))

⚠️ 注意事项：

• 该方法时间复杂度为 O(|N|! × |N| + |N|! × |H|)，适用于 |N| ≤ 8 的小规模场景；若 N 较长（如 > 10），需改用滑动窗口 + 字符频次统计（如 Counter）的线性解法，避免生成全排列。
• input().strip() 可防止首尾空格干扰；
• set(permutations(N)) 依赖元组的不可变性与哈希性，对纯字母字符串完全安全；
• 不推荐在循环中重复调用 "".join(...) 多次——当前已优化为每次只拼一次。

总结：核心在于理解“distinct permutations”的本质是去重后的排列集合，而非全排列数量；善用 set 和语义化命名，即可写出准确、可读、健壮的解决方案。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《统计唯一排列子串的高效方法》文章吧，也可关注golang学习网公众号了解相关技术文章。