原题链接在这里:https://leetcode.com/problems/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
Constraints:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i]
contains only lower case English letters.
题解:
In the arr, s could contain duplicate character. These strings with duplicate characters can't be used.
Have a list to maintain all previous bit masks. When checking a new string s, check all previous bit masks, if there is not intersection, then s could be used.
Update the maximum result and add the new bitmast into list.
Time Complexity: expontential.
Space: expontential.
AC Java:
1 class Solution { 2 public int maxLength(List<String> arr) { 3 int res = 0; 4 List<Integer> candidates = new ArrayList<>(); 5 candidates.add(0); 6 7 for(String s : arr){ 8 int dup = 0; 9 int sBit = 0; 10 for(char c : s.toCharArray()){ 11 dup |= sBit & 1<<(c-'a'); 12 sBit |= 1<<(c-'a'); 13 } 14 15 if(dup > 0){ 16 continue; 17 } 18 19 for(int i = 0; i<candidates.size(); i++){ 20 if((candidates.get(i) & sBit) > 0){ 21 continue; 22 } 23 24 candidates.add(candidates.get(i) | sBit); 25 res = Math.max(res, Integer.bitCount(candidates.get(i) | sBit)); 26 } 27 } 28 29 return res; 30 } 31 }