What is the main pattern used in Maximum Length of a Concatenated String with Unique Characters?

The core pattern is backtracking search with pruning, checking character uniqueness via a bitmask.

Can I use sets instead of bitmasks?

Yes, sets work for tracking used characters, but bitmasks are faster and use less memory.

How does pruning help in this problem?

Pruning stops recursion early when a string would introduce duplicate characters, saving exponential computations.

What is the maximum array length constraint?

The input array length is between 1 and 16, which allows backtracking without exceeding reasonable computation time.

Do I need to check for duplicates inside a single string?

Yes, strings with repeated characters cannot contribute to a valid unique-character concatenation.

#1239

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

串联字符串的最大长度

给定一个字符串数组 arr ，字符串 s 是将 arr 的含有不同字母的子序列字符串连接所得的字符串。请返回所有可行解 s 中最长长度。子序列是一种可以从另一个数组派生而来的数组，通过删除某些元素或不删除元素而不改变其余元素的顺序。示例 1：输入： arr = ["un","i…

数组字符串回溯位运算

题目描述

给定一个字符串数组 arr，字符串 s 是将 arr 的含有 不同字母 的 子序列 字符串连接所得的字符串。

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

子序列 是一种可以从另一个数组派生而来的数组，通过删除某些元素或不删除元素而不改变其余元素的顺序。

示例 1：

输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是：
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
最大长度为 4。

示例 2：

输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。

示例 3：

输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26

提示：

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] 中只含有小写英文字母

lightbulb

解题思路

方法一：状态压缩 + 位运算

由于题目要求子序列的字符不能重复，字符都是小写字母，因此，我们可以用一个长度为 $26$ 的二进制整数来表示一个子序列，其中第 $i$ 位为 $1$ 表示子序列中含有滴 $i$ 个字符，为 $0$ 表示不含有第 $i$ 个字符。

我们可以用一个数组 $s$ 来存储所有满足条件的子序列的状态，初始时 $s$ 中只有一个元素 $0$ 。

然后我们遍历数组 $\textit{arr}$ ，对于每个字符串 $t$ ，我们用一个整数 $x$ 来表示 $t$ 的状态，然后我们遍历数组 $s$ ，对于每个状态 $y$ ，如果 $x$ 和 $y$ 之间没有相同的字符，那么我们将 $x$ 和 $y$ 的并集加入到 $s$ 中，并更新答案。

最后我们返回答案即可。

时间复杂度 $O(2^n + L)$ ，空间复杂度 $O(2^n)$ ，其中 $n$ 是字符串数组的长度，而 $L$ 是字符串数组中所有字符串的长度之和。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        s = [0]
        for t in arr:
            x = 0
            for b in map(lambda c: ord(c) - 97, t):
                if x >> b & 1:
                    x = 0
                    break
                x |= 1 << b
            if x:
                s.extend((x | y) for y in s if (x & y) == 0)
        return max(x.bit_count() for x in s)

speed

复杂度分析

指标	值
时间	complexity is O(2^n * m) where n is arr.length and m is the average string length, due to exploring all subsequences with bitmask checks. Space complexity is O(n) for recursion stack, plus O(1) for bitmask storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate consider character uniqueness across combined strings?
question_mark
Does the solution prune paths where duplicates would occur instead of exploring blindly?
question_mark
Are bitmask techniques or efficient character tracking applied for faster checks?

warning

常见陷阱

外企场景

error
Not checking for duplicate characters inside individual strings before combining.
error
Failing to prune subsequences early, leading to timeouts on larger arrays.
error
Using string concatenation repeatedly instead of a bitmask or set, increasing runtime unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum length where characters can repeat at most k times.
arrow_right_alt
Return all possible concatenated strings with maximum length and unique characters.
arrow_right_alt
Solve the problem when strings contain uppercase letters and digits as well.

help

常见问题

外企场景

继续练习

#1255 得分最高的单词集合 #691 贴纸拼词 #1178 猜字谜