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.

Examples

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.

Constraints

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[i] contains only lowercase English letters.

Problem Analysis

DFS | State Compression using Bit Manipulation

Code Implementation

class Solution {
public:
    int bt[20], ans, n;
    bool getBT(string& s, int* t) {
        for(auto& ch : s) {
            if(((*t) >> (ch - 'a')) & 1) return 0;
            *t += 1 << (ch - 'a');
        }
        return 1;
    }
    int cnt(int num) {
        int ans = 0;
        while(num) {
            num -= (num & -num);
            ++ans;
        }
        return ans;
    }
    void dfs(int st, int alpha, int star) {
        ans = max(ans, cnt(alpha));
        if(ans == 26) return ;
        for(int i = star; i < n; ++i)
            if(!((st >> i) & 1) && (alpha ^ bt[i]) == (alpha + bt[i])) 
                dfs(st + (1 << i), alpha ^ bt[i], i + 1);
    }
    int maxLength(vector<string>& arr) {
        for(int i = 0; i < arr.size();) {
            int t = 0;
            if(getBT(arr[i], &t)) bt[i++] = t;
            else arr.erase(arr.begin () + i);
        }    
        n = arr.size();
        dfs(0, 0, 0);
        return ans;
    }
};

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status