LeetCode 1239. 串联字符串的最大长度

约 11 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 字符串 位运算 回溯
目录

题目描述

✅ 1239. 串联字符串的最大长度

题意分析

从给定的字符串数组里挑出一个子序列，把它们拼接起来，要求拼接结果中每个字符最多出现一次，求这种拼接串的最大长度。

「子序列」意味着可以任选若干个（包括一个都不选，此时长度为 0），且不要求连续。拼接顺序不影响字符集合，也不影响长度，所以顺序完全可以忽略——问题实质是「选一个子集」而不是「排一个序列」。

关键约束有三条：数组长度不超过 16，每个字符串长度不超过 26，且只含小写字母。16 这个数字非常刺眼——$2^{16} = 65536$，直接说明枚举所有子集是可行的，这是一个明确的「指数级枚举可接受」的信号。而「只含小写字母」加上「字符不能重复」意味着任何合法拼接串的长度不超过 26，同时也意味着一个字符串的字符集合可以用 26 位来完整表示。

还有一个容易被忽略的前提：数组中某个字符串自身可能就含有重复字符（比如 "aa"），这种字符串永远不可能被选中，应该在一开始就剔除。

边界：所有字符串自身都含重复字符（答案 0）、只有一个字符串、所有字符串两两冲突（答案是最长的单个串）、数组长度取到上限 16。

解法：位掩码 + 回溯

核心思路

暴力做法是枚举所有 $2^n$ 个子集，对每个子集把选中的字符串拼起来，再用一个计数数组检查有没有重复字符。正确但慢：每次检查都要重新扫一遍所有选中的字符，单次代价 $O(26 \cdot n)$，总代价 $O(2^n \cdot n \cdot 26)$，而且大量工作是重复的——同一个前缀的字符集被反复重算。

瓶颈在于「字符集合」这个中间结果没有被复用，也没有被压缩。观察到：一个只含小写字母且无重复的字符串，其信息量只有「用了哪 26 个字母中的哪些」，完全可以压进一个 int 的低 26 位。压成整数之后，两件事变成了单条指令——判断两个集合是否不相交写成 a & b == 0，把两个集合并起来写成 a | b。

于是预处理阶段把每个字符串转成一个 26 位掩码；转换过程中如果某一位已经被置过，说明字符串自身有重复字符，直接丢弃它。这一步既压缩了表示，又提前剔除了永远无效的候选。

搜索阶段是标准的「选或不选」回溯。定义 dfs(idx, mask) 表示：在下标 idx 及其之后的字符串里继续挑选，且当前已经占用的字符集合是 mask 时，还能额外获得的最大长度。

这个定义的两条不变量是：进入 dfs(idx, mask) 时，mask 恰好是已选字符串掩码的按位或，且这些已选串两两之间字符不重复；返回值只统计 idx 及以后新增的长度，不包含 mask 已经代表的部分。有了这两条，递归的合并就很干净——不选当前串就直接是 dfs(idx+1, mask)，选当前串（前提是 mask & next == 0）就是 lens[idx] + dfs(idx+1, mask | next)，取两者较大值。

因为顺序无关且每个串只在自己那一层被决定一次，天然不会产生重复的子集，不需要额外的同层去重。

解题步骤

  • 预处理每个字符串：逐字符算出 bit = 1 << (c - 'a')，若 mask & bit != 0 说明该字符已出现过，标记这个串无效并跳出；否则 mask |= bit。有效的串把掩码和长度分别存进 masks 和 lens 两个平行数组。为什么要单独存长度：虽然长度等于掩码的二进制中 1 的个数，但直接存下来省掉每次调用 bitCount 的开销，代码也更直白。
  • 提前剔除自身含重复字符的串，是为了让搜索阶段的逻辑保持单一——进入 dfs 后只需要考虑「与已选集合冲突」，不必再考虑「自己内部冲突」。
  • dfs(idx, mask) 的终止条件是 idx == masks.size()，返回 0。返回 0 而不是别的值，是因为返回值的语义是「还能新增多少长度」，没有可选项时新增为 0，这也让它成为 max 的正确起点。
  • 先算「不选当前串」的分支 dfs(idx+1, mask) 作为初始最优值。不选永远合法，所以它可以无条件作为兜底，这保证了 best 一开始就是一个可行解而不是负无穷。
  • 再判断 mask & masks.get(idx) == 0。这一步就是全部的剪枝：与已选集合有任何一个字符重叠，这条分支立刻被砍掉，不会继续递归。冲突越早出现，砍掉的子树越大。
  • 若不冲突，用 lens.get(idx) + dfs(idx+1, mask | next) 与 best 取较大值。传下去的是 mask | next 这个新值，而不是修改后再改回来——因为 mask 是按值传递的参数，天然完成了「进入下一层前做选择、返回后撤销选择」，不需要显式回溯。
  • 从 dfs(0, 0) 开始，初始掩码为 0 表示还没选任何字符串。最终返回值就是答案；全都不选时答案为 0，符合题意。

以 arr = ["un","iq","ue"] 走一遍。预处理："un" 的字符 u、n 互不相同，掩码记作 $M_{un}$，长度 2；"iq" 得 $M_{iq}$，长度 2；"ue" 得 $M_{ue}$，长度 2。三个串都有效。

dfs(0, 0) 先算不选 "un" 的分支 dfs(1, 0)。dfs(1, 0) 再先算不选 "iq" 的 dfs(2, 0)：它先算 dfs(3, 0) = 0，然后发现 0 & M_{ue} == 0，取 2 + dfs(3, M_{ue}) = 2 + 0 = 2，返回 2。回到 dfs(1, 0)，此时 best = 2；再试选 "iq"，0 & M_{iq} == 0 成立，需要 dfs(2, M_{iq})：它先算 dfs(3, M_{iq}) = 0，再判断 M_{iq} & M_{ue}——i、q 与 u、e 无交集，为 0，于是取 2 + 0 = 2，返回 2。所以选 "iq" 这一支得 2 + 2 = 4，dfs(1, 0) 返回 4。

回到 dfs(0, 0)，best = 4。再试选 "un"：0 & M_{un} == 0 成立，算 dfs(1, M_{un})。它先算 dfs(2, M_{un})：先取 dfs(3, M_{un}) = 0，再判断 M_{un} & M_{ue}——两者都含字符 u，结果非零，冲突，这条分支被剪掉，返回 0。回到 dfs(1, M_{un})，试选 "iq"：M_{un} & M_{iq} == 0，得 2 + dfs(2, M_{un} | M_{iq})，而 dfs(2, ...) 中 "ue" 仍与 u 冲突，返回 0，所以这支是 2，dfs(1, M_{un}) 返回 2。于是选 "un" 整支得 2 + 2 = 4。

best = max(4, 4) = 4，返回 4。对应的最优组合有两种："un" + "iq" 和 "iq" + "ue"，长度都是 4，与预期一致。

代码实现

// 先把每个串压成 26 位掩码并剔除自重复串，再按「选或不选」回溯。
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        List<Integer> lens = new ArrayList<>();

        for (String s : arr) {
            int mask = 0;
            boolean ok = true;
            for (int i = 0; i < s.length(); i++) {
                int bit = 1 << (s.charAt(i) - 'a');
                if ((mask & bit) != 0) {
                    ok = false;
                    break;
                }
                mask |= bit;
            }
            if (ok) {
                masks.add(mask);
                lens.add(s.length());
            }
        }

        return dfs(masks, lens, 0, 0);
    }

    private int dfs(List<Integer> masks, List<Integer> lens, int idx, int mask) {
        if (idx == masks.size()) {
            return 0;
        }

        int best = dfs(masks, lens, idx + 1, mask);

        int next = masks.get(idx);
        if ((mask & next) == 0) {
            best = Math.max(best, lens.get(idx) + dfs(masks, lens, idx + 1, mask | next));
        }
        return best;
    }
}

// 先把每个串压成 26 位掩码并剔除自重复串，再按「选或不选」回溯。
func maxLength(arr []string) int {
	masks := make([]int, 0)
	lens := make([]int, 0)

	for _, s := range arr {
		mask := 0
		ok := true
		for i := 0; i < len(s); i++ {
			bit := 1 << (s[i] - 'a')
			if mask&bit != 0 {
				ok = false
				break
			}
			mask |= bit
		}
		if ok {
			masks = append(masks, mask)
			lens = append(lens, len(s))
		}
	}

	return dfs(masks, lens, 0, 0)
}

func dfs(masks []int, lens []int, idx int, mask int) int {
	if idx == len(masks) {
		return 0
	}

	best := dfs(masks, lens, idx+1, mask)

	next := masks[idx]
	if mask&next == 0 {
		val := lens[idx] + dfs(masks, lens, idx+1, mask|next)
		if val > best {
			best = val
		}
	}
	return best
}

复杂度分析

  • 时间复杂度：$O(2^m + \sum \lvert s_i\rvert)$，其中 m 为通过预处理筛选后的有效字符串数量（不超过 16），$\sum \lvert s_i\rvert$ 为所有字符串的总字符数。预处理是一趟线性扫描；搜索每层做「选/不选」两个分支，递归树规模为 $O(2^m)$，每个节点内部只有常数次位运算和比较。
  • 空间复杂度：$O(m)$。masks 和 lens 各存 m 个整数，递归深度最多 m 层、每层只有几个局部变量；掩码本身是单个 int，不随字符集大小增长。

关键点总结

  • 数组长度 ≤ 16 或 ≤ 20 这类极小上界，几乎总是在提示「枚举全部子集是允许的」。看到这个规模先别想多项式算法，直接往 $2^n$ 的方向设计，这是本题最重要的规模判读。
  • 「元素是小写字母且不能重复」等价于「一个 26 位的集合」。把集合压成整数后，交集判空是 a & b == 0、并集是 a | b，两个 $O(26)$ 的操作降到 $O(1)$，这个转换在字符集有限的题里可以无脑套用。
  • 无效候选要在预处理阶段剔除，而不是在搜索里判断。这样搜索函数只需要处理一种冲突（与已选集合冲突），逻辑单一、分支少。
  • 「选或不选」型回溯把状态作为值参数传下去时，回溯是自动完成的，不需要写「做选择—撤销选择」的成对代码。只有当状态是共享的可变结构（数组、列表）时才需要显式撤销。
  • 因为决策按下标顺序逐个做出，每个子集只会被生成一次，所以不需要同层去重。要警惕的是把它错写成「每层从所有未选串里挑一个」的排列式搜索，那样会把同一个子集重复搜 $k!$ 遍。
  • 面试视角：写完回溯后主动指出「还可以改成迭代式子集枚举：外层 for state in 0..2^m，内层检查每一位」，或者「用 dp[mask] 记录该字符集合是否可达」，说明你知道位运算枚举与回溯是同一件事的两种写法，通常能换来加分。

易错点总结

  • 错误写法：预处理时不检查字符串自身是否含重复字符 → arr = ["aa"] 时，"aa" 的掩码只有一位，与空集不冲突，被选中后返回 2，正确答案是 0。
  • 错误写法：用掩码中 1 的个数当长度，但预处理时没剔除自重复串 → arr = ["aa","bc"] 中 "aa" 的掩码只有 1 位，长度被算成 1，答案变成 3，正确答案是 2。
  • 错误写法：冲突判断写成 mask | next != 0 或 mask & next != 0 才递归 → 前者恒成立导致所有串都被选中，arr = ["un","ue"] 会返回 4；后者把判断反了，只有冲突时才递归，答案恒为 0。
  • 错误写法：dfs 的终止条件返回 mask 的位数或当前累计长度 → 返回值语义与「还能新增多少」不一致，arr = ["un","iq","ue"] 中每层都会把已有长度重复累加，答案偏大。
  • 错误写法：只写「选当前串」分支，遗漏「不选」分支 → arr = ["a","abcdef"] 中若先选 "a"，后者会因冲突无法选择，只得到 1；跳过第一个串才能取得正确答案 6。
  • 错误写法：bit = 1 << (s.charAt(i) - 'A') 用大写字母做基准 → 小写字母减去 'A' 得到 32 以上的偏移，1 << 32 在 Java 里等于 1（移位数按 32 取模），掩码全部串位，冲突判断完全失效。
  • 错误写法：每层从所有未使用的字符串里挑一个，用 used 数组标记 → 同一个集合会按不同顺序被搜索多次，arr 长度为 16 时从 $2^{16}$ 膨胀到 $16!$ 量级，直接超时。
  • 错误写法：把 mask 声明成成员变量并在递归中直接修改，返回后忘记恢复 → arr = ["un","iq","ue"] 中试完 "un" 分支后 mask 仍带着 u、n，导致后续的 "iq"、"ue" 组合被错误地判成冲突，答案偏小。
  • 错误写法：预处理时遇到重复字符只 break 而没有用 ok 标记，导致部分掩码仍被加入 → arr = ["aab"] 会把只含 a 的半成品掩码存进去，长度记成 3，答案错误。

相似题目

题目 难度 考察点
78. 子集 中等 同样的「选或不选」框架，但要收集全部方案而非求最值
90. 子集 II 中等 元素可重复，必须先排序再做同层跳过才能避免重复子集
698. 划分为k个相等的子集 中等 状态是 dp[mask] 的桶填充进度，需要按剩余容量剪枝
473. 火柴拼正方形 中等 桶数固定为 4，降序排序与「首根失败即整体失败」是关键剪枝