1239. Maximum Length of a Concatenated String with Unique Characters

题目信息

题号:

1239

难度:

Medium

主题:

字符串、回溯、位掩码、子序列

原题:

LeetCode 1239

重点:

从字符串数组中选择一个子序列并按原顺序连接,最终字符串中的每个字符最多出现一次;允许选择空子序列

题目重述

给定只包含小写英文字母的字符串数组 arr。可以选择其中若干字符串,保持它们在数组中的相对顺序并连接成一个新字符串。

要求连接结果中不存在重复字符。请返回所有合法选择能够得到的最大字符串长度;某个候选字符串自身包含重复字符时不能被选入合法结果。

1 <= arr.length <= 16,1 <= arr[i].length <= 26。

自建示例

最优结果可以跳过与其他字符冲突的字符串:

输入:arr = ["ab","cd","aef"]
输出:5
解释:选择 "cd" 和 "aef" 得到 "cdaef",五个字符互不相同;若同时选择 "ab" 会重复 a。

所有字符串自身都含重复字符时只能选择空子序列:

输入:arr = ["aa","bb"]
输出:0
解释:任意非空选择都会在结果中产生重复字符。