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

原题链接在这里：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:

 class Solution {

     public int maxLength(List<String> arr) {

         int res = 0;

         List<Integer> candidates = new ArrayList<>();

         candidates.add(0);

         for(String s : arr){

             int dup = 0;

             int sBit = 0;

             for(char c : s.toCharArray()){

                 dup |= sBit & 1<<(c-'a');

                 sBit |= 1<<(c-'a');

             }

             if(dup > 0){

                 continue;

             }

             for(int i = 0; i<candidates.size(); i++){

                 if((candidates.get(i) & sBit) > 0){

                     continue;

                 }

                 candidates.add(candidates.get(i) | sBit);

                 res = Math.max(res, Integer.bitCount(candidates.get(i) | sBit));

             }

         }

         return res;

     }

 }

巴特西

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

最新文章

热门文章