1239. Maximum Length of a Concatenated String with Unique Characters
Description
You are given an array of strings arr
. A string s
is formed by the concatenation of a subsequence of arr
that has unique characters.
Return the maximum possible length of s
.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = ["un","iq","ue"] Output: 4 Explanation: All the valid concatenations are: - "" - "un" - "iq" - "ue" - "uniq" ("un" + "iq") - "ique" ("iq" + "ue") Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"] Output: 6 Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"] Output: 26 Explanation: The only string in arr has all 26 characters.
Constraints:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i]
contains only lowercase English letters.
Solutions
Solution 1: State Compression + Bit Manipulation
Since the problem requires that the characters in the subsequence must not be repeated and all characters are lowercase letters, we can use a binary integer of length $26$ to represent a subsequence. The $i$-th bit being $1$ indicates that the subsequence contains the $i$-th character, and $0$ indicates that it does not contain the $i$-th character.
We can use an array $s$ to store the states of all subsequences that meet the conditions. Initially, $s$ contains only one element $0$.
Then we traverse the array $\textit{arr}$. For each string $t$, we use an integer $x$ to represent the state of $t$. Then we traverse the array $s$. For each state $y$, if $x$ and $y$ have no common characters, we add the union of $x$ and $y$ to $s$ and update the answer.
Finally, we return the answer.
The time complexity is $O(2^n + L)$, and the space complexity is $O(2^n)$. Here, $n$ is the length of the string array, and $L$ is the sum of the lengths of all strings in the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|