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

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

题目描述

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

image-20260929075910491

image-20260929075910609

题意分析

从字符串数组中选择若干项，按它们原来的顺序拼接，要求最终字符串中的每个字符最多出现一次，返回能够得到的最大长度。可以跳过任意项，也允许一个都不选。

选择的单位是完整字符串，不能只取其中部分字符。某个字符串内部已经有重复字母时，它本身就不合法；不同字符串之间也不能共享字母。候选最多十六项，字符仅为小写英文字母，可以枚举选择并用位集合快速判断冲突。

解法：位掩码 + 回溯

核心思路

[!blue]

用一个整数的低二十六位表示字母是否出现，第 c - 'a' 位对应字母 c。构建单个字符串的掩码时，若对应位已经为一，说明这个词内部有重复字符，任何拼接方案都不能选它，直接剔除；其余词保存掩码和完整长度。

定义 dfs(idx, mask) 为：前面的选择已经使用 mask 中的字母，从第 idx 个候选往后还能增加的最大长度。返回值不包含已经选中的部分，这让每次选择只在本层加一次当前词长。

对当前候选有两种情况。不选时，掩码不变，递归下一项；选择时必须满足 (mask & next) == 0，即两组字母没有交集，然后用 mask | next 合并集合，返回当前长度加后续最优值。两种结果取最大，完整覆盖当前项选或不选的可能。

下标每层递增，选择顺序始终与输入一致。候选全部处理完时，后面没有可以增加的字符，返回零。掩码按值传入下一层，兄弟分支各有自己的状态，不需要手动清除字母位。

解题步骤

  1. 逐词构建字母掩码，剔除内部含重复字母的候选，保存其余掩码和长度。
  2. 从 dfs(0, 0) 开始，表示尚未处理候选、尚未使用任何字母。
  3. 先求跳过当前项的结果，作为一定可行的初值。
  4. 当前候选与已用集合无交集时，再计算选择它的结果，与初值取最大。
  5. 下标到达候选末尾时返回新增长度零，最外层返回全局最大长度。

代码实现

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);
    }

    // 返回剩余候选还能新增的长度，不包含当前 mask 已有部分。
    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;
    }
}

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)
}

// 返回剩余候选还能新增的长度，不包含当前 mask 已有部分。
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(L+2^m)$，L 为输入总字符数，m 为过滤后的候选数。预处理扫描字符，二叉选择树最多指数级状态，每个状态的位运算为常数。
  • 空间复杂度：$O(m+1)$，保存有效候选掩码、长度和深度至多为 m 的递归栈；没有有效候选时仍有常数开销。

关键点总结

[!green]

  • 掩码只记录是否出现，所以必须先单独排除字符串内部的重复。
  • 与运算判冲突，或运算合并字符集合，避免反复扫描已有拼接结果。
  • 返回后续新增长度，当前词只由选择它的那一层计入一次。
  • 跳过分支始终保留，较早的词不一定属于最优组合。

易错点总结

[!yellow]

  • 只看掩码里的不同字母数，没有检查原词内部重复，会把不合法完整字符串当作候选。
  • 遇到当前可选词就强制选入，它可能阻挡后面更有价值的组合。
  • 在递归终点返回已经选中的总长度，又在外层逐词加长度，造成重复计数。
  • 用或运算是否为零判断冲突，混淆集合合并与交集；无冲突应判断与运算为零。
  • 将掩码改成所有分支共享的可变状态，却没有撤销，会污染其他选择。

相似题目

题目 难度 关联与区别
318. 最大单词长度乘积 中等 同样用字母掩码判断不相交，本题可选多个单词并累计长度，原题只选两个并最大化长度乘积。
784. 字母大小写全排列 中等 同样通过逐项选择生成候选，本题选择整个单词且需验证合并后的字符不重复。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/65561109
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！