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, /*used=*/0);
  }

 private:
  int dfs(const vector<int>& masks, int s, unsigned used) {
    int res = popcount(used);
    for (int i = s; i < masks.size(); ++i)
      if ((used & masks[i]) == 0)
        res = max(res, dfs(masks, i + 1, used | 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.contains() == s.length())
        masks.push_back(mask);
    }

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

 private:
  int dfs(const vector<bitset<26>>& masks, int s, bitset<26> used) {
    int res = used.contains();
    for (int i = s; i < masks.size(); ++i)
      if (!(used & masks[i]).any())
        res = max(res, dfs(masks, i + 1, used | 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<unsigned> masks;

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

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

 private:
  int dfs(const vector<unsigned>& masks, int i, int used) {
    if (i == masks.size())
      return 0;
    const int pick =
        (masks[i] & used) == 0
            ? popcount(masks[i]) + dfs(masks, i + 1, used | masks[i])
            : 0;
    const int skip = dfs(masks, i + 1, used);
    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;
  }
};