串联字符串的最大长度 图解题解

这道题到底在问什么

输入

arr=["un","iq","ue"]

输出

4

输入

arr=["cha","r","act","ers"]

输出

6

输入

arr=["aa","bb"]

输出

0

最优解：一步一步想明白

1. 3核心三句话：串变指纹、按位与为 0 才能拼、DFS 选与不选并随时刷新最大长度。下面每帧都在套它。
2. 4把每个串压成字母集先扫一遍数组，把每个串变成它用到的字母集合（指纹）。指纹相当于这个串占用了哪些字母。
3. 5"un" → {un}"un" 内部没有重复字母，合法。它占用的字母集是 {u、n}，记下这枚指纹。
4. 6"iq" → {iq}"iq" 内部没有重复字母，合法。它占用的字母集是 {i、q}，记下这枚指纹。
5. 7"ue" → {ue}"ue" 内部没有重复字母，合法。它占用的字母集是 {u、e}，记下这枚指纹。
6. 8长度 0从空串出发，还没选任何串，长度 0。接下来逐个候选串试着往里选。
7. 9"un" 指纹 & 当前 = 0试候选 "un"（占用 {u、n}）。它和当前已选 空串 没有公共字母，按位与为 0，可以选入。
8. 10长度 2当前已串联 "un"，长度 2，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 2。
9. 11"iq" 指纹 & 当前 = 0试候选 "iq"（占用 {i、q}）。它和当前已选 "un" 没有公共字母，按位与为 0，可以选入。
10. 12长度 4当前已串联 "uniq"，长度 4，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
11. 13公共字母 {u}试候选 "ue"，但它和当前已选 "uniq" 共用字母 {u}，按位与不为 0，会重复，排除掉、不选它。
12. 14退回 "un"选入 "iq" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 "un"，再去试下一个候选。
13. 15公共字母 {u}试候选 "ue"，但它和当前已选 "un" 共用字母 {u}，按位与不为 0，会重复，排除掉、不选它。
14. 16退回 "空串"选入 "un" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 空串，再去试下一个候选。
15. 17"iq" 指纹 & 当前 = 0试候选 "iq"（占用 {i、q}）。它和当前已选 空串 没有公共字母，按位与为 0，可以选入。
16. 18长度 2当前已串联 "iq"，长度 2，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
17. 19"ue" 指纹 & 当前 = 0试候选 "ue"（占用 {u、e}）。它和当前已选 "iq" 没有公共字母，按位与为 0，可以选入。
18. 20长度 4当前已串联 "ique"，长度 4，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
19. 21退回 "iq"选入 "ue" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 "iq"，再去试下一个候选。
20. 22退回 "空串"选入 "iq" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 空串，再去试下一个候选。
21. 23"ue" 指纹 & 当前 = 0试候选 "ue"（占用 {u、e}）。它和当前已选 空串 没有公共字母，按位与为 0，可以选入。
22. 24长度 2当前已串联 "ue"，长度 2，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
23. 25退回 "空串"选入 "ue" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 空串，再去试下一个候选。
24. 26答案 = 4决策树全部走完。所有合法组合里最长的是 "uniq"（"un"+"iq"）或 "ique"（"iq"+"ue"），长度都是 4，这就是最终答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def maxLength(self, arr: List[str]) -> int:
        masks = []
        for s in arr:
            mask = 0
            ok = True
            for ch in s:
                bit = 1 << (ord(ch) - 97)
                if mask & bit:
                    ok = False; break
                mask |= bit
            if ok:
                masks.append((mask, len(s)))
        ans = 0
        def dfs(i, mask, length):
            nonlocal ans
            ans = max(ans, length)
            for j in range(i, len(masks)):
                m, l = masks[j]
                if mask & m == 0:
                    dfs(j + 1, mask | m, length + l)
        dfs(0, 0, 0)
        return ans

#include <string>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maxLength(vector<string>& arr) {
        vector<pair<int,int>> masks;
        for (auto &s : arr) {
            int mask = 0; bool ok = true;
            for (char c : s) { int bit = 1 << (c - 'a'); if (mask & bit) { ok = false; break; } mask |= bit; }
            if (ok) masks.push_back({mask, (int)s.size()});
        }
        int ans = 0;
        function<void(int,int,int)> dfs = [&](int i, int mask, int len) {
            ans = max(ans, len);
            for (int j = i; j < (int)masks.size(); ++j) if ((mask & masks[j].first) == 0) dfs(j + 1, mask | masks[j].first, len + masks[j].second);
        };
        dfs(0, 0, 0);
        return ans;
    }
};

import java.util.*;
class Solution {
    List<int[]> masks;
    int ans;
    public int maxLength(List<String> arr) {
        masks = new ArrayList<>();
        for (String s : arr) {
            int mask = 0; boolean ok = true;
            for (char c : s.toCharArray()) {
                int bit = 1 << (c - 'a');
                if ((mask & bit) != 0) { ok = false; break; }
                mask |= bit;
            }
            if (ok) masks.add(new int[]{mask, s.length()});
        }
        ans = 0; dfs(0, 0, 0);
        return ans;
    }
    private void dfs(int i, int mask, int len) {
        ans = Math.max(ans, len);
        for (int j = i; j < masks.size(); j++) if ((mask & masks.get(j)[0]) == 0) dfs(j + 1, mask | masks.get(j)[0], len + masks.get(j)[1]);
    }
}

复杂度

面试官可能追问