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 <= 161 <= arr[i].length <= 26arr[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.
Python3
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)
Java
class Solution {
public int maxLength(List<String> arr) {
List<Integer> s = new ArrayList<>();
s.add(0);
int ans = 0;
for (var t : arr) {
int x = 0;
for (char c : t.toCharArray()) {
int b = c - 'a';
if ((x >> b & 1) == 1) {
x = 0;
break;
}
x |= 1 << b;
}
if (x > 0) {
for (int i = s.size() - 1; i >= 0; --i) {
int y = s.get(i);
if ((x & y) == 0) {
s.add(x | y);
ans = Math.max(ans, Integer.bitCount(x | y));
}
}
}
}
return ans;
}
}
C++
class Solution {
public:
int maxLength(vector<string>& arr) {
vector<int> s = {0};
int ans = 0;
for (const string& t : arr) {
int x = 0;
for (char c : t) {
int b = c - 'a';
if ((x >> b & 1) == 1) {
x = 0;
break;
}
x |= 1 << b;
}
if (x > 0) {
for (int i = s.size() - 1; i >= 0; --i) {
int y = s[i];
if ((x & y) == 0) {
s.push_back(x | y);
ans = max(ans, __builtin_popcount(x | y));
}
}
}
}
return ans;
}
};
Go
func maxLength(arr []string) (ans int) {
s := []int{0}
for _, t := range arr {
x := 0
for _, c := range t {
b := int(c - 'a')
if (x>>b)&1 == 1 {
x = 0
break
}
x |= 1 << b
}
if x > 0 {
for i := len(s) - 1; i >= 0; i-- {
y := s[i]
if (x & y) == 0 {
s = append(s, x|y)
ans = max(ans, bits.OnesCount(uint(x|y)))
}
}
}
}
return ans
}
TypeScript
function maxLength(arr: string[]): number {
const s: number[] = [0];
let ans = 0;
for (const t of arr) {
let x = 0;
for (const c of t) {
const b = c.charCodeAt(0) - 97;
if ((x >> b) & 1) {
x = 0;
break;
}
x |= 1 << b;
}
if (x > 0) {
for (let i = s.length - 1; ~i; --i) {
const y = s[i];
if ((x & y) === 0) {
s.push(x | y);
ans = Math.max(ans, bitCount(x | y));
}
}
}
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}