Medium

题目描述

给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中只包含唯一字符，那么它是可行的。

请返回所有可行解 s 中最长长度。

子序列是一个可以从另一个数组中删除某些或不删除元素而不改变其余元素顺序的数组。

示例 1：

输入：arr = ["un","iq","ue"]
输出：4
解释：所有的合法串连接是 ""，"un"，"iq"，"ue"，"uniq" 和 "ique"。
最大长度为 4。

示例 2：

输入：arr = ["cha","r","act","ers"]  
输出：6
解释：可能的最长有效串连接是 "chaers"（"cha" + "ers"）和 "acters"（"act" + "ers"）。

示例 3：

输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26
解释：数组中唯一的字符串包含所有 26 个字符。

提示：

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

解题思路

这是一个典型的回溯算法问题，需要找到所有可能的字符串组合并计算最大长度。

核心思路：

  1. 预处理过滤：首先筛选出本身就包含重复字符的字符串，这些字符串无法参与有效组合
  2. 回溯搜索：对于每个字符串，我们有两种选择：选择它或不选择它
  3. 状态检查：每次添加新字符串时，检查是否与已选择的字符产生冲突
  4. 优化策略：使用位掩码来高效检查字符重复，每个字符对应一个位

算法流程：

  • 遍历数组中的每个字符串，尝试将其加入当前组合
  • 检查新字符串是否与现有字符集合有重复
  • 如果没有重复，递归处理剩余字符串
  • 回溯时恢复状态，尝试不选择当前字符串的情况
  • 记录过程中的最大长度

时间复杂度主要由状态空间决定，最坏情况下需要遍历所有可能的子集组合。

代码实现

class Solution {
public:
    int maxLength(vector<string>& arr) {
        vector<string> valid;
        // 预处理：过滤掉包含重复字符的字符串
        for (const string& s : arr) {
            if (isValid(s)) {
                valid.push_back(s);
            }
        }
        
        return backtrack(valid, 0, "");
    }
    
private:
    bool isValid(const string& s) {
        vector<bool> used(26, false);
        for (char c : s) {
            if (used[c - 'a']) return false;
            used[c - 'a'] = true;
        }
        return true;
    }
    
    bool hasConflict(const string& s1, const string& s2) {
        vector<bool> used(26, false);
        for (char c : s1) {
            used[c - 'a'] = true;
        }
        for (char c : s2) {
            if (used[c - 'a']) return true;
        }
        return false;
    }
    
    int backtrack(const vector<string>& arr, int index, const string& current) {
        int maxLen = current.length();
        
        for (int i = index; i < arr.size(); i++) {
            if (!hasConflict(current, arr[i])) {
                maxLen = max(maxLen, backtrack(arr, i + 1, current + arr[i]));
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        def is_valid(s):
            return len(s) == len(set(s))
        
        def has_conflict(s1, s2):
            return len(set(s1) & set(s2)) > 0
        
        def backtrack(index, current):
            max_len = len(current)
            
            for i in range(index, len(valid_arr)):
                if not has_conflict(current, valid_arr[i]):
                    max_len = max(max_len, backtrack(i + 1, current + valid_arr[i]))
            
            return max_len
        
        # 过滤掉包含重复字符的字符串
        valid_arr = [s for s in arr if is_valid(s)]
        
        return backtrack(0, "")

public class Solution {
    public int MaxLength(IList<string> arr) {
        var valid = new List<string>();
        
        // 预处理：过滤掉包含重复字符的字符串
        foreach (string s in arr) {
            if (IsValid(s)) {
                valid.Add(s);
            }
        }
        
        return Backtrack(valid, 0, "");
    }
    
    private bool IsValid(string s) {
        var used = new HashSet<char>();
        foreach (char c in s) {
            if (used.Contains(c)) return false;
            used.Add(c);
        }
        return true;
    }
    
    private bool HasConflict(string s1, string s2) {
        var set1 = new HashSet<char>(s1);
        foreach (char c in s2) {
            if (set1.Contains(c)) return true;
        }
        return false;
    }
    
    private int Backtrack(List<string> arr, int index, string current) {
        int maxLen = current.Length;
        
        for (int i = index; i < arr.Count; i++) {
            if (!HasConflict(current, arr[i])) {
                maxLen = Math.Max(maxLen, Backtrack(arr, i + 1, current + arr[i]));
            }
        }
        
        return maxLen;
    }
}

var maxLength = function(arr) {
    function isValid(s) {
        const used = new Set();
        for (let c of s) {
            if (used.has(c)) return false;
            used.add(c);
        }
        return true;
    }
    
    function hasConflict(s1, s2) {
        const set1 = new Set(s1);
        for (let c of s2) {
            if (set1.has(c)) return true;
        }
        return false;
    }
    
    function backtrack(index, current) {
        let maxLen = current.length;
        
        for (let i = index; i < validArr.length; i++) {
            if (!hasConflict(current, validArr[i])) {
                maxLen = Math.max(maxLen, backtrack(i + 1, current + validArr[i]));
            }
        }
        
        return maxLen;
    }
    
    // 过滤掉包含重复字符的字符串
    const validArr = arr.filter(s => isValid(s));
    
    return backtrack(0, "");
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n × m)n为有效字符串数量，m为平均字符串长度，需要遍历所有可能的子集组合
空间复杂度O(n × m)递归栈深度最大为n，每层需要O(m)空间存储字符串状态