LeetCode 1763. Longest Nice Substring 三种 Go 解法详解：分治、二进制状态与暴力枚举

LeetCode 1763. Longest Nice Substring 三种 Go 解法详解分治、二进制状态与暴力枚举【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本题要求在一个长度不超过 100 的字符串中找出最长美好子串Longest Nice Substring——即子串中每个出现的字母都必须同时存在大写和小写两种形式例如abABB是美好的而abA不是。本仓库 LeetCode-Go 在leetcode/1763.Longest-Nice-Substring/目录下提供了三种 Go 实现分治O(n)、二进制状态位运算枚举、以及暴力枚举计数表校验。读完本文你将掌握美好字符串的判定本质、三种解法的完整可运行代码、各自的复杂度特征以及仓库配套测试用例的验证方式。题目定义什么是 Nice 子串根据 题目文档一个字符串s被称为nice美好当且仅当s中包含的每一种字母其大写形式和小写形式都同时出现。abABB是美好字符串A与a同时出现B与b同时出现abA不是美好字符串b出现了但B没有出现。任务要求给定字符串s返回其最长的美好子串若存在多个长度相同的答案返回最早出现的一个若不存在返回空字符串。约束条件1 s.length 100s仅由大写和小写英文字母组成数据规模很小最长为 100因此从暴力枚举到分治的所有解法都能在毫秒级完成这也让本题成为练习同一问题多种解法的绝佳素材。三个官方示例输入输出说明YazaAayaAa子串aAa中唯一出现的字母是A/a大小写同时存在且它是最长的美好子串BbBb整个字符串即美好子串B与b同时出现c长度不足 2单个字母不可能同时拥有大小写两种形式解题思路总览三种解法的设计脉络仓库 README 给出的三种解法覆盖了从最直观到最精巧的完整梯度解法一分治以坏字符为分割点递归地切割字符串把大问题拆成互不相交的左右子问题解法二二进制状态用两个 26 位整数的二进制位记录子串中出现的小写字母集合与大写字母集合lower upper即等价于每个字母大小写成对出现一次比较完成校验解法三暴力枚举枚举所有子串起点与终点用哈希表统计字符频次并逐个校验大小写配对。三者共同回答了同一个核心问题如何高效判定字母大小写是否成对出现。解法三用哈希表逐个比对校验成本高解法二用位掩码一次比较O(1) 校验解法一则干脆跳过无法配对的字母从结构上剪枝。解法一分治Divide and Conquer算法思想核心观察若字符串s中存在某个字母c它只有大写或只有小写形式出现在s中即c无法配对那么任何包含该字母的子串都不可能是美好子串。因此可以以该字母为分割点把问题缩小到它的左右两侧longestNiceSubstring(s) └─ 若 len(s) 2直接返回 单个字符不可能美好 └─ 统计 s 中每个字符出现的次数chars 哈希表 └─ 从左到右扫描 ├─ 若 s[i] 的大写和小写形式都存在于 chars 中 → 继续扫描 └─ 否则 s[i] 是坏字符 ├─ left longestNiceSubstring(s[:i]) ├─ right longestNiceSubstring(s[i1:]) └─ 返回两者中较长者等长取 left保证最早出现 └─ 若全部字符都能配对 → 整个 s 就是答案仓库实现代码源码位于 1763. Longest Nice Substring.gopackage leetcode import unicode // 解法一 分治时间复杂度 O(n) func longestNiceSubstring(s string) string { if len(s) 2 { return } chars : map[rune]int{} for _, r : range s { chars[r] } for i : 0; i len(s); i { r : rune(s[i]) _, u : chars[unicode.ToUpper(r)] _, l : chars[unicode.ToLower(r)] if u l { continue } left : longestNiceSubstring(s[:i]) right : longestNiceSubstring(s[i1:]) if len(left) len(right) { return left } else { return right } } return s }代码关键点解读坏字符的判定unicode.ToUpper(r)与unicode.ToLower(r)分别求出字符r的另一种形式只要二者都在chars中无论出现几次该字母就是可配对的。递归基len(s) 2直接返回——单个字符或空串不可能同时包含大小写。等长取左len(left) len(right)时优先返回左半部分配合从左到右扫描坏字符的顺序天然保证了题目要求的多个答案返回最早出现的一个。正确性根源坏字符被排除在两侧之外而左右两侧互不包含该字符因此所有美好子串必然完整落在左侧或右侧问题得以无损地递归拆解。解法二二进制状态位运算O(1) 校验算法思想由于字母表只有 26 个字母可以用一个 26 位整数的第 k 位表示第 k 个字母是否出现过。对每个以i为起点的子串维护两个掩码lower出现过的小写字母集合第s[j]-a位置 1upper出现过的大写字母集合第s[j]-A位置 1。若lower upper说明对于任意一个字母只要小写形式出现大写形式也出现反之亦然——这正是美好子串的判定条件且只需一次整数比较时间复杂度 O(1)。仓库实现代码// 解法二 用二进制表示状态 func longestNiceSubstring1(s string) (ans string) { for i : range s { lower, upper : 0, 0 for j : i; j len(s); j { if unicode.IsLower(rune(s[j])) { lower | 1 (s[j] - a) } else { upper | 1 (s[j] - A) } if lower upper j-i1 len(ans) { ans s[i : j1] } } } return }代码关键点解读大小写分支unicode.IsLower判断字符是否为小写据此选择更新lower或upper掩码位运算1 (s[j] - a)将字符映射到 025 的位下标。成对判定即位相等例如子串aAalower的第 0 位为 1upper的第 0 位也为 1两者相等 → 美好而abA中lower有第 0、1 位upper只有第 0 位不相等 → 不美好。严格更长才更新条件j-i1 len(ans)用严格大于意味着同长度的更早子串不会被覆盖满足返回最早出现的一个。复杂度双指针枚举所有子串 O(n²)但每次校验是 O(1) 的位比较相比解法三的哈希表校验常数更小。解法三暴力枚举 计数表校验算法思想最直观的做法枚举所有子串s[i:j1]把子串字符放入哈希表m然后调用checkNiceString检查每一个出现的字母是否大小写成对。虽然校验成本高但由于s.length 100最坏 O(n³) 也完全可接受。仓库实现代码// 解法三 暴力枚举时间复杂度 O(n^2) func longestNiceSubstring2(s string) string { res : for i : 0; i len(s); i { m : map[byte]int{} m[s[i]] for j : i 1; j len(s); j { m[s[j]] if checkNiceString(m) (j-i1 len(res)) { res s[i : j1] } } } return res } func checkNiceString(m map[byte]int) bool { for k : range m { if k 97 k 122 { if _, ok : m[k-32]; !ok { return false } } if k 65 k 90 { if _, ok : m[k32]; !ok { return false } } } return true }代码关键点解读ASCII 差值技巧小写字母与大写字母的 ASCII 码恰好相差 32如a97、A65。k-32表示k对应的大写形式k32表示对应的小写形式。这里用数值区间[97,122]、[65,90]代替unicode包判断避免了类型转换。增量式哈希内层循环每扩展一个字符只做一次m[s[j]]复用了外层已统计的频次信息避免为每个子串重新构建哈希表。校验语义checkNiceString遍历所有出现过的字符若小写字母缺少对应大写m[k-32]不存在或大写字母缺少对应小写m[k32]不存在立即判定失败全部配对才返回true。复杂度的诚实标注README 中标注解法三为 O(n²)从源码结构看加上每次checkNiceString对哈希表的全量遍历实际最坏约为 O(n³)但受限于 n ≤ 100 依然高效。三种解法对比解法核心技巧校验方式时间复杂度的官方标注代码位置解法一 分治坏字符剪枝、递归切分大小写掩码查表O(n)longestNiceSubstring解法二 二进制状态26 位掩码位运算lower upper一次比较枚举 O(n²)单次校验 O(1)longestNiceSubstring1解法三 暴力枚举哈希表频次统计逐字母校验 ASCII ±32 配对O(n²)longestNiceSubstring2checkNiceString三者输出一致都返回最长且最早出现的那个美好子串。测试验证表驱动用例与执行方式仓库为本题提供了完整的表驱动测试 1763. Longest Nice Substring_test.go结构如下type question1763 struct { para1763 ans1763 } // para 是参数 // one 代表第一个参数 type para1763 struct { s string } // ans 是答案 // one 代表第一个答案 type ans1763 struct { one string }测试用例与 LeetCode 官方示例一一对应para1763{YazaAay}→ 期望ans1763{aAa}para1763{Bb}→ 期望ans1763{Bb}para1763{c}→ 期望ans1763{}Test_Problem1763在循环中同时调用了longestNiceSubstring、longestNiceSubstring1与longestNiceSubstring2三个版本用fmt.Printf打印输入输出仓库测试采用输出比对配合人工核对的方式。本地执行该用例的命令为go test -v -run Test_Problem1763 ./leetcode/1763.Longest-Nice-Substring/若想验证整个仓库的覆盖率可参照根目录 gotest.sh 的做法一次性对./leetcode/...生成覆盖率报告go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库的模块名为github.com/halfrost/LeetCode-Go见 go.modGo 版本要求 1.19所有题解代码统一放在package leetcode包中可直接作为参考实现复用。延伸思考位掩码的通用性解法二的思路可以推广到字母集合类题目——只要字母表规模固定26就能用整数位表示集合把集合相等退化为整数相等。本题的lower upper判定本质上是把每个字母成对出现压缩成了一次 32 位整数比较。分治的剪枝威力解法一在存在坏字符时立刻递归避免了对包含坏字符的无效子串的冗余枚举从源码结构看其递归深度与坏字符数量正相关最坏情况下如全串只有一个坏字符且位于中间会接近 O(n²)但平均表现优异这也是 README 将其标注为 O(n) 的依据。判定条件的等价性三种解法从三个角度验证了同一个数学事实——子串美好 ⇔ 小写字母集合 大写字母集合。理解这一等价关系是写出正确、优雅解法的关键。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考