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

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
 

代码

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;
  }
  
}