freeCodeCamp 每日编程挑战 Challenge 270：用 JavaScript 找出字符串中最长重复子串-平芜编程栈

freeCodeCamp 每日编程挑战 Challenge 270：用 JavaScript 找出字符串中最长重复子串

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp

本篇基于 freeCodeCamp 课程库中的 JavaScript 每日编程挑战（Daily Coding Challenge）第 270 题Longest Common Substring，完整讲解题目要求、全部测试用例与官方参考解法，并结合仓库中的课程结构、挑战类型定义和 API 路由说明这道题在 freeCodeCamp 体系中的位置。读完后你可以掌握：用「长度从大到小 + 双端索引定位」求解最长重复子串的经典思路，理解indexOf/lastIndexOf判重的技巧与「允许重叠」这一题眼带来的边界差异。

题目定位与课程元信息

该题的挑战文件为 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69cfca90e8a0a6d4d6871c54.md，其 YAML 头部的关键元信息如下：

字段	取值	含义
`id`	`69cfca90e8a0a6d4d6871c54`	挑战全局唯一标识（MongoDB ObjectId 风格）
`title`	`Challenge 270: Longest Common Substring`	每日挑战按天编号，本题为第 270 天
`challengeType`	`28`	挑战类型，`28`对应 JavaScript 每日挑战
`dashedName`	`challenge-270`	用于生成页面路由的短横线名称

其中challengeType: 28的语义可以在共享包中直接确认：packages/shared/src/config/challenge-types.ts 定义了const dailyChallengeJs = 28;与const dailyChallengePy = 29;，即 JavaScript 版与 Python 版每日挑战各占一个类型编号。

题目在课程目录中的挂载位置由块（block）结构文件 curriculum/structure/blocks/daily-coding-challenges-javascript.json 的challengeOrder数组决定，其中：

{ "id": "69cfca90e8a0a6d4d6871c54", "title": "Challenge 270: Longest Common Substring" }

从该结构文件顶部还可以看到块级配置"usesMultifileEditor": true和"disableLoopProtectTests": true——后者值得注意：每日挑战中经常出现需要多轮扫描字符串的题目，若测试框架的循环保护（loop protect）生效会误杀合法的多重循环解法，因此该块显式关闭了这项保护。

此外，freeCodeCamp 的 API 侧有专门的每日挑战信息接口，路由实现见 api/src/daily-coding-challenge/routes/daily-coding-challenge.ts，提供/daily-coding-challenge/today、/daily-coding-challenge/date/:date、/daily-coding-challenge/month/:month等端点，按美国中部时间（US Central）的 UTC 零点切分「今天」，并以 Prisma 查询dailyCodingChallenges模型返回当日挑战；挑战的提交本身仍走主 API 的挑战完成路由（该插件的 JSDoc 中有明确说明）。

题目要求

题目描述（继承自原文档）：

Given a string, return the longest substring that appears more than once.
The substrings can overlap.

翻译成中文：给定一个字符串，返回其中出现次数大于 1 的最长子串。题眼是第二行——子串允许重叠。

这一点直接排除了「先按空白切词找重复词」之类的偷懒解法。比如mississippi的正确答案"issi"就出现在两个重叠的位置：

m i s s i s s i p p i └─issi─┘ └─issi─┘

两处"issi"各占下标 2 起和下标 4 起，共享中间的"ssi"。

全部测试用例

原文档给出了 5 条断言，构成完整的验收标准（原文使用assert.equal形式）：

assert.equal(getLongestSubstring("abracadabra"), "abra"); assert.equal(getLongestSubstring("hello world hello"), "hello"); assert.equal(getLongestSubstring("mississippi"), "issi"); assert.equal(getLongestSubstring("ha ha ha ha ha ha ha"), "ha ha ha ha ha ha"); assert.equal( getLongestSubstring("the quick brown fox jumped over the lazy dog that the quick brown fox jumped over"), "the quick brown fox jumped over" );

逐条看，它们分别覆盖了不同的考察面：

"abracadabra"→"abra"：开头与结尾各出现一次，无重叠，是最基本的整段重复；
"hello world hello"→"hello"：重复片段被其他内容隔开；
"mississippi"→"issi"：重叠重复的典型样例，验证「允许重叠」规则；
"ha ha ha ha ha ha ha"（21 字符，7 次"ha "结构）→"ha ha ha ha ha ha"（18 字符）：重复单元是短小且高频的"ha "，答案可以横跨几乎整个字符串，验证长跨度窗口；
长句样例：重复片段本身含空格且长度接近原串一半，验证答案可以包含空白字符、长度不受限制。

起点代码（seed）

挑战在编辑器中给出的初始骨架是挑战文件的--seed--段：

function getLongestSubstring(str) { return str; }

函数签名为getLongestSubstring(str)，参数名固定为str，需要自行实现整个算法。

官方参考解法完整解读

原文档--solutions--段给出的参考答案完整如下：

function getLongestSubstring(str) { let longest = ''; for (let len = str.length - 1; len >= 1; len--) { for (let i = 0; i <= str.length - len; i++) { const sub = str.slice(i, i + len); if (str.indexOf(sub) !== str.lastIndexOf(sub)) { return sub; } } } return longest; }

核心策略：长度从大到小，首次命中即返回

算法骨架是一个双层循环，外层控制候选子串的长度len，从str.length - 1递减到1；内层控制起始下标i，从0扫到str.length - len（保证slice(i, i + len)不越界）。

之所以外层长度递减，是因为题目要的是「最长」：一旦某个长度下找到了出现两次的子串，更短的候选就没有资格成为答案，函数可以立即return sub结束，不需要继续枚举。这使该解法在答案较长（如长句样例）时往往只需扫描一两层长度就能退出。

同时，内层i从小到大扫描带来一个确定的平局规则：同长度有多个不同答案时，返回的是起始位置最靠左的那个。例如"hello world hello"中"hello"只有一种取法，但如果输入是"abxabxab"，长度 6 层会先在i = 0处命中"abxabx"，直接返回，而不会继续考虑其他位置。

判重技巧：`indexOf`与`lastIndexOf`对比

判重的判断条件是解法中最精炼的一处：

if (str.indexOf(sub) !== str.lastIndexOf(sub)) { return sub; }

String.prototype.indexOf(sub)返回sub第一次出现的下标，String.prototype.lastIndexOf(sub)返回最后一次出现的下标。两个值相等意味着sub至多只出现一次；两个值不等，说明它至少在两个不同位置出现过，即「出现次数大于 1」。

这个写法避免了显式统计出现次数的辅助结构。从源码结构看，它还有一个隐含行为：内层循环构造的sub本身必然存在（就是原串的一段），所以indexOf不会返回-1的边界情况，两个下标都是合法的非负值，比较逻辑是安全的。

另外注意重叠场景下indexOf/lastIndexOf也成立——它们做的是逐下标子串匹配，并不要求两次出现互不重叠，这正是题目「The substrings can overlap」所需要的语义。

边界行为

无重复子串：两层循环跑完（len减到1仍无命中）时，函数返回初始值longest，即空字符串''。例如getLongestSubstring("abc")会得到''。longest变量在这个解法里实际只承担「兜底返回值」的职责，从未被重新赋值；
空串输入：str.length - 1为-1，外层循环条件len >= 1不成立，直接落入return longest返回''，不会抛错；
答案就是整个串去头/去尾：len从str.length - 1起步（而不是str.length），因为整串只出现一次，不可能满足「出现两次」，起点取length - 1是安全的上界。

复杂度与进一步优化方向

该参考解法每层长度下最多枚举约n个窗口，每个窗口用indexOf/lastIndexOf做最长O(n)的匹配，最坏情况下（如全相同字符或完全没有重复）复杂度约为O(n^3)量级。对于每日挑战的输入规模，朴素实现足以通过全部断言。

若追求更高效的实现，可以沿两个方向改进（以下属于基于该题约束的常规算法延伸，非仓库内容）：

哈希分组法：固定长度len，把所有窗口的哈希值（或窗口字符串本身）存入Map<string, number[]>，只保留每个值第一次出现的下标；若再次命中相同键即说明重复，长度递减扫描下首个命中即答案。用哈希把单次窗口查重降到均摊O(1)，整体可到O(n^2)量级；
后缀数组 / 滚动哈希 + 二分：对长度做二分，配合滚动哈希判断「该长度是否存在重复窗口」，可达接近O(n log n)。但这类方案需要处理哈希冲突（双模数或取原串验证），实现复杂度明显更高，面试白板场景用长度递减排列的朴素解法更易沟通。

对本题而言，官方解法的价值在于用最少的机制（两个内置方法 + 双层循环）覆盖了全部 5 个测试用例，包括重叠与长跨度场景。

与 Python 版本的对照

freeCodeCamp 的每日挑战采用「同题双语」的组织方式：同一id（69cfca90e8a0a6d4d6871c54）在 Python 块中也存在对应文件 curriculum/challenges/english/blocks/daily-coding-challenges-python/69cfca90e8a0a6d4d6871c54.md，其challengeType: 29（即上文提到的dailyChallengePy），题目描述、5 组用例与本题完全一致，只是断言改经runPython执行 Python 单测，且函数命名为蛇形的get_longest_substring。Python 参考解法与 JS 版逐行对应：

def get_longest_substring(s): longest = '' for length in range(len(s) - 1, 0, -1): for i in range(len(s) - length + 1): sub = s[i:i + length] if s.find(sub) != s.rfind(sub): return sub return longest

对照两者可以清楚看到 API 映射关系：JS 的str.slice(i, i + len)对应 Python 切片s[i:i + length]；JS 的indexOf/lastIndexOf对应str.find/str.rfind。两个语言版本共享同一套「长度递减 + 双端定位」算法，是理解本题思路的良好交叉参照。

小结与延伸阅读

本题的核心考点有三个，可归纳为：

搜索顺序即答案保证：外层长度从大到小，使得「第一次命中即返回」天然满足「最长」要求，无需记录并比较候选；
indexOf/lastIndexOf差值判重：用首末出现位置是否分离来判断「出现多次」，避免计数结构；
允许重叠的匹配语义：内置子串匹配不做重叠限制，"mississippi"→"issi"的重叠用例正是对这一语义的验收。

仓库中可继续深入的相关位置：块结构与块级配置见 curriculum/structure/blocks/daily-coding-challenges-javascript.json；挑战类型编号体系见 packages/shared/src/config/challenge-types.ts；每日挑战的查询端点见 api/src/daily-coding-challenge/routes/daily-coding-challenge.ts；课程挑战文件的字段规范（如challengeType取值范围 0–33）可在 curriculum/schema/challenge-schema.js 中查阅。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

freeCodeCamp 每日编程挑战 Challenge 270：用 JavaScript 找出字符串中最长重复子串