1239. Maximum Length of a Concatenated String with Unique Characters

⭐️⭐️⭐️

# 題目敘述

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.

# 解題思路

# Solution

import java.util.ArrayList;

import java.util.List;

class Solution {

    public int maxLength(List<String> arr) {

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

        list.add(0);

        int res = 0;

        for (String str : arr) {

            int strValue = 0, checkSame = 0;

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

                checkSame |= strValue & (1 << (c - 'a'));

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

            }

            if (checkSame > 0)

                continue;

            for (int i = list.size() - 1; i >= 0; i--) {

                if ((list.get(i) & strValue) > 0)

                    continue;

                list.add(list.get(i) | strValue);

                res = Math.max(res, Integer.bitCount(list.get(i) | strValue));

            }

        }

        return res;

    }

}