企业官网建设流程全解析

LeetCode-Go 题解 1239：位掩码 + DFS 求解最大无重复字符连接串长度

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 LeetCode-Go 仓库中 1239. Maximum Length of a Concatenated String with Unique Characters 题解文档 为主体，深入剖析该题"将字符串映射为 26 位二进制掩码 + 深度优先搜索枚举子序列"的经典解法。读完本文，你将掌握如何用uint32位掩码高效表示字符集合、如何用按位与运算做冲突检测，以及如何基于仓库内的源码与测试用例独立验证算法正确性。

题目描述

给定一个字符串数组arr。字符串s是由arr中某个子序列（sub-sequence）的字符串拼接（concatenation）而成，并且s中的每个字符都必须是唯一的（unique characters）。

请返回满足条件的s的最大可能长度（maximum possible length）。

示例

示例 1：

输入：arr = ["un","iq","ue"] 输出：4 解释：所有可能的拼接结果是 ""、"un"、"iq"、"ue"、"uniq" 和 "ique"。 最大长度为 4。

示例 2：

输入：arr = ["cha","r","act","ers"] 输出：6 解释：可行解为 "chaers" 和 "acters"。

示例 3：

输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26

约束条件

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i]仅包含小写英文字母

核心思路：把字符串压缩成 26 位二进制掩码

题目对"唯一字符"的要求非常严格：拼接结果s中任何字符都不能重复出现。由于输入仅包含小写英文字母（共 26 个），我们可以把每个字符串压缩为一个 26 位的二进制串（mask）：

• 字符串中出现过的字符，对应位标记为 1；
• 字符串中未出现的字符，对应位标记为 0。

这一映射有两条极其有用的性质：

1. 自重复检测：如果一个字符串内部本身就含有重复字符，那么它掩码中 1 的个数一定不等于字符串长度。因此len(s) != bits.OnesCount32(mask)可以直接判断该字符串是否"自洁"。
2. 互不冲突检测：如果两个字符串各自的字符都不重复，且它们拼接后仍不产生重复字符，那么这两个掩码按位与的结果必然为 0（mask1 & mask2 == 0），说明二者的 1 位完全不重叠、字符集合互补。

借助这两条性质，我们可以把"字符串拼接"这个看似字符串层面的操作，完全降维成整数的按位与 / 按位或运算，再配合深度优先搜索枚举所有可行子序列组合，即可求出最长可行解的长度。

算法流程分解

第一步：构建掩码并过滤自重复字符串

对应仓库源码 题解实现 中的maxLength函数前半段：

c, res := []uint32{}, 0 for _, s := range arr { var mask uint32 for _, c := range s { mask = mask | 1<<(c-'a') // 将字符 c 对应的位标记为 1 } if len(s) != bits.OnesCount32(mask) { // 如果字符串本身带有重复的字符，需要排除 continue } c = append(c, mask) }

关键细节：

• c - 'a'将字符转换为 0～25 的索引，1<<(c-'a')得到该字符对应的唯一二进制位；
• bits.OnesCount32(mask)来自 Go 标准库math/bits，统计 32 位整数中 1 的个数，即字符串中不同字符的数量；
• 若len(s) != bits.OnesCount32(mask)，说明字符串内部有重复字符，这类字符串不可能出现在任何可行解中（因为拼接结果要求每个字符唯一），直接跳过。

这一步是重要的剪枝：arr中可能混入"aa"、"abab"这类自身就带重复的字符串，提前过滤可以显著缩小后续 DFS 的搜索空间。

第二步：DFS 枚举所有互不冲突的子序列

过滤完成后，问题转化为：在掩码数组c中，选取若干互不冲突（两两按位与为 0）的掩码，使所有选中掩码的 1 位总数最大。这正是典型的子集枚举问题，用深度优先搜索解决：

func dfs(c []uint32, index int, mask uint32, res *int) { *res = max(*res, bits.OnesCount32(mask)) for i := index; i < len(c); i++ { if mask&c[i] == 0 { dfs(c, i+1, mask|c[i], res) } } return }

搜索策略要点：

• index表示从掩码数组的哪个位置开始继续选取，保证每个子序列组合只被枚举一次（组合而非排列，顺序无关）；
• mask & c[i] == 0是可行性剪枝：当前已选字符集合与候选字符串的字符集合无交集时，才允许拼接；
• 选中后通过mask | c[i]合并字符集合，传入下一层递归；
• 每进入一层，都用bits.OnesCount32(mask)统计当前拼接串长度（因为所有字符唯一，1 的个数就是字符串长度），并更新全局最大值*res。

入口调用为dfs(c, 0, 0, &res)：从空集出发，初始掩码为 0，最长长度为 0。

完整 Go 实现

以下代码与仓库 题解实现文件 完全一致（增加中文注释）：

package leetcode import ( "math/bits" ) func maxLength(arr []string) int { c, res := []uint32{}, 0 for _, s := range arr { var mask uint32 for _, c := range s { mask = mask | 1<<(c-'a') // 标记字符 c 在掩码中对应的位 } if len(s) != bits.OnesCount32(mask) { // 如果字符串本身带有重复的字符，需要排除 continue } c = append(c, mask) } dfs(c, 0, 0, &res) return res } func dfs(c []uint32, index int, mask uint32, res *int) { *res = max(*res, bits.OnesCount32(mask)) for i := index; i < len(c); i++ { if mask&c[i] == 0 { // 两个掩码按位与为 0，说明字符集合互补，可以拼接 dfs(c, i+1, mask|c[i], res) } } return } func max(a, b int) int { if a > b { return a } return b }

实现细节：仓库 go.mod 声明 Go 版本为 1.19，该版本标准库尚未提供内置的max泛型函数（Go 1.21 才引入），因此题解在包内自行定义了max(a, b int) int辅助函数。

测试用例与运行验证

仓库为本题提供了完整的单元测试文件 1239 测试用例，采用本仓库统一的"参数-答案"结构组织测试数据：

package leetcode import ( "fmt" "testing" ) type question1239 struct { para1239 ans1239 } // para 是参数 // one 代表第一个参数 type para1239 struct { arr []string } // ans 是答案 // one 代表第一个答案 type ans1239 struct { one int } func Test_Problem1239(t *testing.T) { qs := []question1239{ { para1239{[]string{"un", "iq", "ue"}}, ans1239{4}, }, { para1239{[]string{"cha", "r", "act", "ers"}}, ans1239{6}, }, { para1239{[]string{"abcdefghijklmnopqrstuvwxyz"}}, ans1239{26}, }, { para1239{[]string{"aa", "bb"}}, ans1239{0}, }, } fmt.Printf("------------------------Leetcode Problem 1239------------------------\n") for _, q := range qs { _, p := q.ans1239, q.para1239 fmt.Printf("【input】:%v 【output】:%v\n", p, maxLength(p.arr)) } fmt.Printf("\n\n\n") }

除了题目给出的 3 个示例，测试还额外覆盖了一个重要的边界用例：

• ["aa", "bb"]→ 0：两个字符串内部都含重复字符，过滤后掩码数组为空，DFS 不会产生任何拼接结果，最终返回 0。这验证了"空拼接串 "" 也是合法可行解"的边界情形——所有字符串都被排除时，最长长度为 0。

仓库根目录的 gotest.sh 提供了统一的多包覆盖率测试命令：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

也可以只针对本题所在包运行：

go test -v ./leetcode/1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters/

复杂度分析

• 时间复杂度：掩码构建阶段遍历每个字符串的每个字符，为 O(N × L)，其中 N =len(arr)≤ 16，L ≤ 26（字符串最长 26 个不同小写字母）；DFS 阶段最坏情况下（所有字符串自身无重复且两两互不冲突）需要枚举全部 2^N 种子集组合，即 O(2^N)。由于 N ≤ 16，搜索空间最多 65536 种状态，规模极小。
• 空间复杂度：掩码数组存储 O(N) 个uint32，DFS 递归深度最多 N，总空间复杂度 O(N)。

关键点总结

1. 26 位掩码是本题的核心抽象：uint32整数即可完整表达任意小写字母字符串的字符集合，比较与合并都退化为常数时间的位运算。
2. 两条判定准则：bits.OnesCount32(mask)与字符串长度比较可排除自重复字符串；mask & c[i] == 0可判定两个字符串拼接后是否仍满足唯一性。
3. DFS 保证枚举完备性：以索引递增的方式遍历掩码数组，确保每个可行子序列组合恰好被考虑一次，配合冲突剪枝，规模极小的 N（≤ 16）下可轻松穷举出全局最优解。
4. 边界情形：所有字符串均被过滤时返回 0，空串也是合法可行解，仓库测试用例["aa", "bb"] → 0对此做了明确验证。

该"位掩码 + DFS/回溯"的组合是算法面试中处理小规模子集枚举 + 字符唯一性约束类问题的通用范式，理解本题的掩码抽象与剪枝策略后，可迁移到类似的字符串子序列、子集组合类问题中。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go