Python排列问题排查：统计子串中不同排列数结果不符预期

核心问题分析 #

给定N=aab（其不同排列仅3种：aab、aba、baa），H=abacabaa中符合条件的排列只有aba（出现2次）和baa（出现1次），正确结果应为2。实际输出4，说明代码存在典型逻辑错误，以下是具体排查方向和修复方案：

常见错误点及排查 #

1. 未对匹配的排列去重，统计了匹配次数而非不同排列数 #

• 错误表现：代码遍历H中所有长度为len(N)的子串，每匹配一个符合字符计数的子串就直接累加计数，而非记录不同的排列后统计数量。比如两次aba被计为2次，加上baa的1次，再加上某个错误匹配的1次，最终得到4。
• 修复思路：使用**集合（Set）**存储匹配到的子串，利用集合自动去重的特性，最终返回集合的大小即可。

2. 字符计数逻辑错误，导致不符合的子串被误判 #

• 错误表现：代码判断子串是否为N的排列时，字符统计有误。例如误将aca（字符计数a:2, c:1）判定为符合N的a:2, b:1，或是未严格匹配字符的种类和数量。
• 修复思路：用字符频率对比的方式判断，比如Python中可以用collections.Counter快速对比：Counter(substring) == Counter(N)，确保两者字符种类和出现次数完全一致。

3. 生成排列时未去重，重复排列被多次统计 #

• 错误表现：代码生成N的全排列时，未处理重复字符的情况，生成了重复排列（比如aab的排列会生成两个aba、两个baa），后续统计时将这些重复项当成不同排列计入。
• 修复思路：生成排列时用集合存储，自动去重，比如unique_permutations = set(itertools.permutations(N))。

修复示例（Python） #

from collections import Counter

def count_unique_permutation_substrings(N, H):
    n_len = len(N)
    h_len = len(H)
    if n_len > h_len:
        return 0
    
    target_counter = Counter(N)
    matched_permutations = set()
    
    # 遍历所有符合长度的子串
    for i in range(h_len - n_len + 1):
        substring = H[i:i+n_len]
        if Counter(substring) == target_counter:
            matched_permutations.add(substring)
    
    return len(matched_permutations)

# 测试输入
N = "aab"
H = "abacabaa"
print(count_unique_permutation_substrings(N, H))  # 输出2，符合预期

验证逻辑 #

遍历H的所有3长度子串，仅aba和baa的字符计数与aab一致；通过集合存储匹配结果自动去重，最终集合大小为2，与预期输出一致。

内容的提问来源于stack exchange，提问作者Ibrahim Kasim