# 1239. Maximum Length of a Concatenated String with Unique Characters
###### tags: `Leetcode` `Medium` `Bit Manipulation` `BackTracking`
Link: https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
## 思路
先找出本身就没有重复字符的字串们 然后算bitmask
然后做backtracking 找出答案
用```haveSameCharacter()```判断两个mask有没有重复的字符
## Code

class Solution {
    int maxLen = 0;
    public int maxLength(List<String> arr) {
        List<Integer> len = new ArrayList<>();
        List<Integer> masks = new ArrayList<>();
        for(String str:arr){
            int mask = mask(str);
            if(mask!=-1){
                masks.add(mask);
                len.add(str.length());
            }
        }
        backtracking(masks, len, 0, 0, 0);
        return maxLen;
    }
    
    private void backtracking(List<Integer> masks, List<Integer> len, int currMask, int currLen, int start){
        for(int i=start; i<masks.size(); i++){
            if(!haveSameCharacter(currMask, masks.get(i))){
                backtracking(masks, len, currMask|masks.get(i), currLen+len.get(i), i+1);
            }
        }
        maxLen = Math.max(maxLen, currLen);
    }
    
    private boolean haveSameCharacter(int mask1, int mask2){
        for(int i=0; i<26; i++){
            if(((mask1>>i)&1)==1 && ((mask2>>i)&1)==1){
                return true;
            }
        }
        return false;
    }
    
    private int mask(String str){
        int mask = 0;
        for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            if(((mask>>(c-'a'))&1)==1) return -1;
            mask += 1<<(c-'a');
        }
        return mask;
    }
}