Skip to content

1239. Maximum Length of a Concatenated String with Unique Characters 👍

Approach 1: DFS

  • Time: $O(2^n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  int maxLength(vector<string>& arr) {
    vector<int> masks;

    for (const string& s : arr) {
      const int mask = getMask(s);
      if (mask != -1)
        masks.push_back(mask);
    }

    return dfs(masks, 0, /*usedMask=*/0);
  }

 private:
  int dfs(const vector<int>& masks, int s, int usedMask) {
    int res = __builtin_popcount(usedMask);
    for (int i = s; i < masks.size(); ++i)
      if ((usedMask & masks[i]) == 0)
        res = max(res, dfs(masks, i + 1, usedMask | masks[i]));
    return res;
  }

  int getMask(const string& s) {
    int mask = 0;
    for (const char c : s) {
      const int i = c - 'a';
      if ((mask & (1 << i)) != 0)
        return -1;
      mask |= 1 << i;
    }
    return mask;
  }
};

Approach 2: DFS w/ std::bitset

  • Time: $O(2^n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int maxLength(vector<string>& arr) {
    vector<bitset<26>> masks;

    for (const string& s : arr) {
      const bitset<26> mask = getMask(s);
      if (mask.count() == s.length())
        masks.push_back(mask);
    }

    return dfs(masks, 0, /*usedMask=*/bitset<26>());
  }

 private:
  int dfs(const vector<bitset<26>>& masks, int s, bitset<26> usedMask) {
    int res = usedMask.count();
    for (int i = s; i < masks.size(); ++i)
      if (!(usedMask & masks[i]).any())
        res = max(res, dfs(masks, i + 1, usedMask | masks[i]));
    return res;
  }

  bitset<26> getMask(const string& s) {
    bitset<26> mask;
    for (const char c : s)
      mask.set(c - 'a');
    return mask;
  }
};

Approach 3: DFS w/ pick/skip pattern

  • Time: $O(2^n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int maxLength(vector<string>& arr) {
    vector<int> masks;

    for (const string& s : arr) {
      const int mask = getMask(s);
      if (mask != -1)
        masks.push_back(mask);
    }

    return dfs(masks, 0, /*usedMask=*/0);
  }

 private:
  int dfs(const vector<int>& masks, int i, int usedMask) {
    if (i == masks.size())
      return 0;
    const int pick = (masks[i] & usedMask) == 0
                         ? __builtin_popcount(masks[i]) +
                               dfs(masks, i + 1, usedMask | masks[i])
                         : 0;
    const int skip = dfs(masks, i + 1, usedMask);
    return max(pick, skip);
  }

  int getMask(const string& s) {
    int mask = 0;
    for (const char c : s) {
      const int i = c - 'a';
      if ((mask & (1 << i)) != 0)
        return -1;
      mask |= 1 << i;
    }
    return mask;
  }
};