Maximum Length of a Concatenated String with Unique Characters LeetCode solution in C++

1
/*
2
1. Create a integer vector, where each integer's bits represent, if a particular
3
char is present or not
4
2. Loop each word in the array and set each bit, create bit map of each word
5
3. Use recursion to add each word with take once and not to take once type dp
6
recursion
7
4. A word can only be taken if its bits are not overlaping with the current
8
string's bit status
9
   - to do this, we need to check if there sum is equal to bit wise andding of
10
them, if eaual then there is no overlaping, if not equal then there is
11
overlaping
12
5. Also we don't have to take the word which has repeted char ( if we have set
13
it to INT_MAX )
14
6. Finally if i is less then 0, check the size of the s with the ans and take
15
maximum
16
*/
17

18
class Solution {
19
 public:
20
  int ans = 0;
21
  void solve(vector<int> &v, vector<string> &arr, int i, string s, int status) {
22
    if (i < 0) {
23
      ans = max(ans, (int)s.size());
24
    } else {
25
      solve(v, arr, i - 1, s, status);
26
      if ((v[i] != INT_MAX) && ((v[i] + status) == (v[i] | status))) {
27
        solve(v, arr, i - 1, s + arr[i], status | v[i]);
28
      }
29
    }
30
  }
31

32
  int maxLength(vector<string> &arr) {
33
    vector<int> v(arr.size());
34
    for (int i = 0; i < arr.size(); ++i) {
35
      for (auto c : arr[i]) {
36
        if ((v[i] >> (c - 'a')) & 1) { // if already bit is set, then set value to INT_MAX
37
          v[i] = INT_MAX;
38
        } else { // if not set, then set it to 1
39
          v[i] = v[i] | (1 << (c - 'a'));
40
        }
41
      }
42
    }
43
    string s = "";
44
    solve(v, arr, arr.size() - 1, s, 0);
45
    return ans;
46
  }
47
};