freeCodeCamp 算法挑战解析：No Repeats Please 的排列生成与相邻去重计数

本篇指南基于 freeCodeCamp 官方课程中的 "No Repeats Please" 经典 JavaScript 算法题（挑战源文件），完整讲解题目要求、全部测试断言、官方参考解法，并结合仓库中的挑战 schema 与题目类型定义，剖析该挑战在 freeCodeCamp 平台中的实际运行机制。读完后你能够：手写递归全排列生成器、用正则完成相邻重复字符的过滤计数，并理解这道题在 freeCodeCamp 课程体系中"从内容文件到可运行挑战"的完整落地链路。

一、题目定义与位置

"No Repeats Please"（请勿重复）要求：给定一个字符串，返回其中不存在连续重复字母的排列总数。题目假设提供的字符串中每个字符各自唯一（即只考虑字母是否相同，而非字符对象是否相同）。

题目的原始描述为：

Return the number of total permutations of the provided string that don't have repeated consecutive letters. Assume that all characters in the provided string are each unique.

例如 aab 应该返回 2：它一共有 6 个排列（aab、aab、aba、aba、baa、baa，其中因两个 a 相同导致 aba 与 aab/baa 各有重复出现），但只有 aba（出现 2 次）不含相邻重复的 a。

在课程结构上，这道题属于 algorithms 模块（block），该模块位于 algorithms.json 定义的 10 道挑战中，紧随 "Inventory Update" 之后、"Pairwise" 之前，而 algorithms 模块又被 coding-interview-prep.json 这个超块（superblock）引用，是 "Coding Interview Prep" 认证课程（算法方向）的组成部分：

// curriculum/structure/superblocks/coding-interview-prep.json
{
  "blocks": ["algorithms", "data-structures", "take-home-projects"]
}

二、完整测试断言（--hints-- 区块）

挑战文件中的 --hints-- 区块即为用户提交后自动运行的测试集。完整的 10 条断言如下（原文逐条继承）：

// 1. 返回值必须是数字类型
assert.isNumber(permAlone('aab'));

// 2. aab → 2
assert.strictEqual(permAlone('aab'), 2);

// 3. aaa → 0（所有排列都含相邻 a）
assert.strictEqual(permAlone('aaa'), 0);

// 4. aabb → 8
assert.strictEqual(permAlone('aabb'), 8);

// 5. abcdefa → 3600
assert.strictEqual(permAlone('abcdefa'), 3600);

// 6. abfdefa → 2640
assert.strictEqual(permAlone('abfdefa'), 2640);

// 7. zzzzzzzz → 0（8 个相同字符，必然相邻重复）
assert.strictEqual(permAlone('zzzzzzzz'), 0);

// 8. 单字符 a → 1
assert.strictEqual(permAlone('a'), 1);

// 9. aaab → 0
assert.strictEqual(permAlone('aaab'), 0);

// 10. aaabb → 12
assert.strictEqual(permAlone('aaabb'), 12);

这些断言覆盖了几个关键边界：

• 类型检查（isNumber）：防止返回字符串或其他 truthy 值蒙混过关；
• 全重复字符（aaa、zzzzzzzz）：答案必为 0；
• 单字符（a）：答案为 1，验证空递归/基线情况；
• 中等规模输入（abcdefa 共 7 字符、5040 个全排列）：用于检验算法能否在可接受时间内完成 n! 级枚举。

三、种子代码与官方参考解法

用户在编辑器中拿到的初始代码（--seed-contents-- 区块）是一个待实现的空壳：

function permAlone(str) {
  return str;
}

permAlone('aab');

官方参考解法（--solutions-- 区块）由两部分组成：一个递归全排列生成器 permuter 和一个正则过滤计数器 permAlone。完整代码如下（原文逐行继承）：

function permAlone(str) {
  return permuter(str).filter(function(perm) {
    return !perm.match(/(.)\1/g);
  }).length;
}

function permuter(str) {
  // http://staff.roguecc.edu/JMiller/JavaScript/permute.html
  //permArr: Global array which holds the list of permutations
  //usedChars: Global utility array which holds a list of "currently-in-use" characters
  var permArr = [], usedChars = [];
  function permute(input) {
    //convert input into a char array (one element for each character)
    var i, ch, chars = input.split("");
    for (i = 0; i < chars.length; i++) {
      //get and remove character at index "i" from char array
      ch = chars.splice(i, 1);
      //add removed character to the end of used characters
      usedChars.push(ch);
      //when there are no more characters left in char array to add, add used chars to list of permutations
      if (chars.length === 0) permArr[permArr.length] = usedChars.join("");
      //send characters (minus the removed one from above) from char array to be permuted
      permute(chars.join(""));
      //add removed character back into char array in original position
      chars.splice(i, 0, ch);
      //remove the last character used off the end of used characters array
      usedChars.pop();
    }
  }
  permute(str);
  return permArr;
}

permAlone('aab');

3.1 排列生成器 permuter 的工作原理

permute 采用的是一种经典的"取一放一"递归策略：

1. 将输入字符串 split("") 成字符数组 chars；
2. 依次把每个索引 i 处的字符 splice(i, 1) 取出并压入 usedChars（当前正在构建的排列前缀）；
3. 若取出后 chars 为空，说明前缀已构成长度等于原串的完整排列，join("") 后写入 permArr；
4. 否则把剩余字符（chars.join("")）递归传入 permute；
5. 递归返回后回溯：chars.splice(i, 0, ch) 把字符放回原位，usedChars.pop() 弹出该层前缀。

两个细节值得注意：

• permArr 与 usedChars 是 permuter 函数体内的闭包变量（代码注释称之为 "Global"，实际上作用域仅限一次 permuter 调用，每次调用都会得到全新的两个数组，无跨调用污染）；
• 该生成器不去重：对 aabb 会枚举出 4! = 24 个字符级排列（每个"真实"排列因两个 a、两个 b 的互换而重复出现 2!×2! = 4 次）。这正是 permAlone("aabb") 返回 8 而非 4 的原因——题目语义是字符级排列计数，abab 和 baba 这两个真实合法排列各被计 4 次。

3.2 正则过滤 !perm.match(/(.)\1/g)

/ (.)\1/g 是相邻重复检测的核心：(.) 捕获任意一个字符，\1 反向引用要求紧接着的下一个字符与之相同，g 标志保证扫描整个字符串。只要排列中存在任意一对相邻相同字符，match 返回非 null，取逻辑非后该排列被 filter 丢弃；filter 保留下来的数组长度即为答案。

对 aaa：全部 6 个字符级排列都含 aa 子串，结果为 0；对 a：唯一排列 a 不含相邻重复，结果为 1。与测试断言完全吻合。

四、复杂度分析与适用前提

从源码结构看，参考解法的复杂度由两段构成：

• 排列生成：permute 的时间与空间均为 O(n!)，因为要物化全部 n! 个长度为 n 的排列字符串；splice 对数组的插拔还引入每层 O(n) 的额外开销；
• 过滤计数：对每个 O(n) 长度的排列做正则匹配，总代价 O(n × n!)。

由此可以推断该解法适用的输入规模：n = 7（如 abcdefa，5040 个排列）在浏览器/Node 测试环境中毫无压力；n = 8 的 zzzzzzzz 有 40320 个排列，依然可以通过。这也是官方测试集只设置到 8 字符的原因。对更长输入，应改用"合法排列直接计数"（含重复字符的排列数用分治/容斥处理相邻约束），避免物化全部排列——但就本题的测试规模而言，参考解法已足够。

五、该挑战在平台中的运行机制（仓库源码佐证）

这个 Markdown 文件并非静态文档，而是被 freeCodeCamp 的构建管线解析为一道可交互挑战。结合仓库源码可以确认以下事实：

1. 文件格式由 schema 校验。 该文件的 frontmatter 字段（id、title、challengeType、forumTopicId、dashedName）符合 challenge-schema.js 的 Joi 约束，其中 challengeType: Joi.number().min(0).max(33).required() 要求类型必须是 0–33 的整数。

2. challengeType: 1 的语义。 在 challenge-types.ts 中，1 对应 const js = 1，即"经典 JavaScript 题目"。同一文件中的 viewTypes 将其映射为 'classic' 视图（经典代码编辑器界面），submitTypes 映射为 'tests' 提交类型——这解释了为什么 --hints-- 区块中的 assert 断言会在用户点击保存/提交时在沙箱中执行：1 号类型的提交路径就是"跑测试"。

3. 挑战在课程中的定位由结构文件声明。 algorithms.json 的 challengeOrder 数组中明确包含：

{
  "id": "a7bf700cd123b9a54eef01d5",
  "title": "No Repeats Please"
}

该 id 与题目 Markdown 的 frontmatter id 一一对应，构建工具据此将内容文件挂载到 "Coding Interview Prep" 认证的 algorithms 模块中，按数组顺序排布在 "Inventory Update" 之后。

六、解题思路小结

1. 基线思维：暴力枚举全部 n! 排列，正则 / (.)\1 /g 过滤含相邻重复者，计数即答案——官方解法即此思路，且注意是字符级计数（重复字符会产生重复排列串）；
2. 可优化点：生成器可改为迭代（Heap 算法/Johnson–Trotter），或用 Set 去重后再计数（但需自行除以重复度以对齐题目期望值）；
3. 边界自查：全部字符相同返回 0、单字符返回 1、返回值必须是数字类型——这三条正是官方测试最先覆盖的场景；
4. 运行方式：在 freeCodeCamp 的课程页面中进入 "Coding Interview Prep" → "Algorithms" 模块即可在线作答；若本地克隆仓库，该题的完整定义（描述、测试、种子、参考解法）集中于 a7bf700cd123b9a54eef01d5.md 一个文件，--description--、--hints--、--seed--、--solutions-- 四个区块分别对应题目描述、测试集、编辑器初始代码与参考答案。