Comment on page

1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters

1239. Maximum Length of a Concatenated String with Unique Characters

题目地址

题目描述

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.
​
Return the maximum possible length of s.
​
Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.
​
Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".
Example 3:
​
Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

代码

Approach 1: Bit Operation

class Solution {
public int maxLength(List<String> arr) {
List<Integer> dp = new ArrayList<>();
dp.add(0);
int res = 0;
for (String s : arr) {
int a = 0, dup = 0;
for (char c : s.toCharArray()) {
dup |= a & (1 << (c - 'a'));
a |= 1 << (c - 'a');
}
if (dup > 0) continue;
for (int i = dp.size() - 1; i >= 0; i--) {
if ((dp.get(i) & a) > 0) continue;
dp.add(dp.get(i) | a);
res = Math.max(res, Integer.bitCount(dp.get(i) | a));
}
}
return res;
}
}

Approach #2 DFS

class Solution {
private int result = 0;
public int maxLength(List<String> arr) {
if (arr == null || arr.length == 0) return 0;
​
dfs(arr, "", 0);
return result;
}
​
private void dfs(List<String> arr, String path, int idx) {
boolean isUniqueChar = isUniqueChars(path);
​
if (isUniqueChar) {
result = Math.max(path.length(), result);
}
​
if (idx == arr.size() || !isUniqueChar) {
return;
}
​
for (int i = idx; i < arr.size(); i++) {
dfs(arr, path + arr.get(i), i + 1);
}
​
}
​
private boolean isUniqueChars(String s) {
Set<Character> set = new HashSet<>();
for (char c : s.toCharArray()) {
if (set.contains(c)) {
return false;
}
set.add(c);
}
return true;
}
​
}