Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 24

Description

Maximum Length of a Concatenated String with Unique Characters

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.

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.

Solution

class Solution {
  int answer = 0;
  int len;
  vector<int> masks;
  vector<int> lens;
  void init(vector<string>& arr) {
    len = arr.size();
    masks.resize(len);
    lens.resize(len);

    for(int i = 0; i < len; ++i) {
      lens[i] = arr[i].length();
      for(auto c : arr[i]) {
        int m = (1 << (c - 'a'));
        if(m & masks[i]) {
          masks[i] = 0;
          lens[i] = 0;
          break;
        }
        masks[i] |= m;
      }
    }
  }

  void solve(int index = 0, int mask = 0, int length = 0) {
    if(index == len) {
      if(length > answer) answer = length;
      return;
    }
    solve(index + 1, mask, length);
    if(lens[index] && (masks[index] & mask) == 0) {
      solve(index + 1, mask | masks[index], length + lens[index]);
    }
  }
public:
  int maxLength(vector<string>& arr) {
    init(arr);
    solve();
    return answer;
  }
};

// Accepted
// 89/89 cases passed (4 ms)
// Your runtime beats 95.93 % of cpp submissions
// Your memory usage beats 92.84 % of cpp submissions (8.1 MB)