1. 项目背景与核心价值小红的好排列这个题目最初出现在牛客网的每日一题栏目中是算法竞赛中典型的排列组合问题。这类题目在互联网大厂的笔试面试中出现频率极高尤其是涉及字符串操作和数学推导的题型。我在刷题过程中发现很多同学面对排列类问题时容易陷入暴力枚举的误区而实际上这类问题往往存在巧妙的数学规律。通过系统分析这道题我们可以掌握排列问题的通用解法模板这对准备技术面试的同学来说价值巨大。2. 问题定义与数学建模2.1 题目重述给定一个由小写字母组成的字符串s定义好排列为排列后的字符串中相邻字符不相同的排列方式。要求计算给定字符串s的所有好排列数量。示例 输入aab 输出2 解释可能的排列为aba、aab、baa其中aba和baa满足条件2.2 问题转化这个问题可以转化为典型的排列组合问题首先计算不考虑限制条件时的全排列数然后减去存在相邻重复的排列数难点在于如何高效计算非法排列的数量3. 解法思路与算法选择3.1 暴力回溯法不推荐最直观的思路是生成所有排列然后筛选from itertools import permutations def count_good_arrangements(s): unique_perms set(permutations(s)) count 0 for p in unique_perms: valid True for i in range(len(p)-1): if p[i] p[i1]: valid False break if valid: count 1 return count时间复杂度O(n!*n)完全不可行3.2 数学推导法推荐更聪明的做法是利用容斥原理计算总排列数n!/(count[a]!count[b]!...)计算至少有一对相邻相同的排列数使用容斥原理计算合法排列数具体推导过程合法排列 总排列 - 至少一对相邻相同 至少两对相邻相同 - 至少三对相邻相同 ...3.3 动态规划解法定义dp[mask][last]表示mask已使用的字符集合位掩码last最后一个使用的字符索引值该状态下的合法排列数转移方程 对于所有未使用的字符i如果s[i] ! s[last]则 dp[mask|(1i)][i] dp[mask][last]4. 最优解实现与代码解析4.1 数学方法实现from math import factorial from collections import Counter def count_good_arrangements(s): n len(s) total factorial(n) for cnt in Counter(s).values(): total // factorial(cnt) # 这里需要实现容斥原理的计算 # 实际实现较为复杂需要生成所有重复字符的组合 # 完整实现参见下方代码仓库链接 return total - invalid_count4.2 动态规划实现def count_good_arrangements(s): n len(s) memo {} def dp(mask, last): if mask (1 n) - 1: return 1 if (mask, last) in memo: return memo[(mask, last)] res 0 for i in range(n): if not (mask (1 i)) and (last -1 or s[i] ! s[last]): res dp(mask | (1 i), i) memo[(mask, last)] res return res return dp(0, -1)5. 复杂度分析与优化5.1 时间复杂度数学方法O(n^2)需要计算各种字符组合动态规划O(n^2 * 2^n)n≤20时可行5.2 空间优化动态规划可以使用滚动数组优化空间def count_good_arrangements(s): n len(s) dp [[0]*n for _ in range(1n)] for i in range(n): dp[1i][i] 1 for mask in range(1n): for last in range(n): if not (mask (1last)): continue for i in range(n): if mask (1i) or s[i] s[last]: continue dp[mask|(1i)][i] dp[mask][last] return sum(dp[(1n)-1][i] for i in range(n))6. 测试用例与边界处理6.1 典型测试用例test_cases [ (a, 1), # 单个字符 (aa, 0), # 全相同字符 (aab, 2), # 牛客示例 (abc, 6), # 全不同字符 (aabbcc, 90) # 多个重复字符 ]6.2 特殊边界处理空字符串返回0全相同字符当n1时返回0全不同字符返回n!超长字符串n20需要数学方法7. 实际应用与扩展7.1 实际应用场景密码生成避免连续重复字符数据编码确保传输稳定性游戏设计随机地图生成7.2 问题变种环形排列首尾也不能相同部分字符必须/不能相邻多组禁止相邻规则提示这类排列问题在亚马逊、谷歌的面试中出现频率很高建议掌握模板解法8. 刷题建议与学习资源推荐练习题目LeetCode 996正方形数组的数目LeetCode 1079活字印刷LeetCode 1411给N×3网格图涂色的方案数学习资源《算法导论》组合数学章节牛客网专项练习题库LeetCode排列组合标签我在实际刷题中发现这类问题的关键在于识别问题本质排列/组合/子集选择合适的剪枝策略处理重复元素的去重合理使用记忆化优化对于准备面试的同学建议每天至少完成2道排列组合类题目培养数学直觉和编码手感。