{"id":5792,"date":"2019-10-27T20:56:41","date_gmt":"2019-10-28T03:56:41","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5792"},"modified":"2019-10-29T00:04:08","modified_gmt":"2019-10-29T07:04:08","slug":"leetcode-1239-maximum-length-of-a-concatenated-string-with-unique-characters","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1239-maximum-length-of-a-concatenated-string-with-unique-characters\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters"},"content":{"rendered":"\n

Given an array of strings arr<\/code>. String s<\/code> is a concatenation of a sub-sequence of arr<\/code> which have unique characters<\/strong>.<\/p>\n\n\n\n

Return the maximum possible length<\/em> of s<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> arr = [\"un\",\"iq\",\"ue\"]\nOutput:<\/strong> 4\nExplanation:<\/strong> All possible concatenations are \"\",\"un\",\"iq\",\"ue\",\"uniq\" and \"ique\".\nMaximum length is 4.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [\"cha\",\"r\",\"act\",\"ers\"]\nOutput:<\/strong> 6\nExplanation:<\/strong> Possible solutions are \"chaers\" and \"acters\".\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [\"abcdefghijklmnopqrstuvwxyz\"]\nOutput:<\/strong> 26\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= arr.length <= 16<\/code><\/li>
  • 1 <= arr[i].length <= 26<\/code><\/li>
  • arr[i]<\/code> contains only lower case English letters.<\/li><\/ul>\n\n\n\n
    Solution: Combination + Bit<\/strong><\/h2>\n\n\n\n
    Time complexity: O(2^n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxLength(vector& arr) {\n    vector a;\n    \n    for (const string& x : arr) {\n      set s(begin(x), end(x));\n      if (s.size() != x.length()) continue;\n      a.push_back(0);      \n      for (char c : x) a.back() |= 1 << (c - 'a');      \n    }\n    \n    int ans = 0;\n    \n    function dfs = [&](int s, int cur) {\n      ans = max(ans, __builtin_popcount(cur));\n      for (int i = s; i < a.size(); ++i)\n        if ((cur & a[i]) == 0)\n          dfs(i + 1, cur | a[i]);      \n    };\n    \n    dfs(0, 0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: DP<\/p>\n\n\n\n
    Time complexity: O(2^n)
    Space complexity: O(2^n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxLength(vector& arr) {\n    vector a;\n    \n    for (const string& x : arr) {\n      int mask = 0;      \n      for (char c : x) mask |= 1 << (c - 'a');\n      if (__builtin_popcount(mask) != x.length()) continue;\n      a.push_back(mask);\n    }\n    \n    int ans = 0;\n    \n    vector dp{0};\n    for (int i = 0; i < a.size(); ++i) {\n      int size = dp.size();\n      for (int j = 0; j < size; ++j) {\n        if (dp[j] & a[i]) continue;\n        int t = dp[j] | a[i];        \n        dp.push_back(t);\n        ans = max(ans, __builtin_popcount(t));\n      }\n    }\n    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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:…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[16,122,33,177,515,42],"class_list":["post-5792","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bit","tag-combination","tag-dfs","tag-medium","tag-o2n","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5792","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5792"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5792\/revisions"}],"predecessor-version":[{"id":5794,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5792\/revisions\/5794"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5792"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5792"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}