freeCodeCamp 每日编程挑战 Challenge 270用 JavaScript 找出字符串中最长重复子串【免费下载链接】freeCodeCampfreeCodeCamp.orgs 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 头部的关键元信息如下字段取值含义id69cfca90e8a0a6d4d6871c54挑战全局唯一标识MongoDB ObjectId 风格titleChallenge 270: Longest Common Substring每日挑战按天编号本题为第 270 天challengeType28挑战类型28对应 JavaScript 每日挑战dashedNamechallenge-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 ha21 字符7 次ha 结构→ha ha ha ha ha ha18 字符重复单元是短小且高频的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把所有窗口的哈希值或窗口字符串本身存入Mapstring, number[]只保留每个值第一次出现的下标若再次命中相同键即说明重复长度递减扫描下首个命中即答案。用哈希把单次窗口查重降到均摊O(1)整体可到O(n^2)量级后缀数组 / 滚动哈希 二分对长度做二分配合滚动哈希判断「该长度是否存在重复窗口」可达接近O(n log n)。但这类方案需要处理哈希冲突双模数或取原串验证实现复杂度明显更高面试白板场景用长度递减排列的朴素解法更易沟通。对本题而言官方解法的价值在于用最少的机制两个内置方法 双层循环覆盖了全部 5 个测试用例包括重叠与长跨度场景。与 Python 版本的对照freeCodeCamp 的每日挑战采用「同题双语」的组织方式同一id69cfca90e8a0a6d4d6871c54在 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 中查阅。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考