This is the 19th day of my participation in the Genwen Challenge

Topic describes

Given an array of strings arr, the string S is the concatenated string of some subsequence of ARR. If every character in S occurs only once, then it is a viable solution.

Return the longest length of all possible solutions s.

Example 1:

Input: arr = [" UN ", and "IQ", "ue"] output: 4: all possible series combination is ""," UN ", and "IQ", "ue", "uniq" and "ique", the maximum length of 4.Copy the code

Example 2:

Input: arr = ["cha","r","act","ers"] Output: 6 Explanation: Possible solutions are "chaers" and "acters".Copy the code

Example 3:

Input: arr = [" abcdefghijklmnopqrstuvwxyz "] output: 26Copy the code

Tip:

  • 1 < =arr.length< = 16
  • 1 < =arr[i].length< = 26
  • arr[i]Contains only lowercase English letters

Their thinking

We need to calculate the length of the feasible solution, and we don’t have to worry about what the feasible solution is, or the order of the characters in the feasible solution. Therefore, each string that constitutes a feasible solution can be treated as a set of characters, and the set contains no repeating elements.

Since the string that makes up the feasible solution contains only lowercase letters and no repeating elements, we can represent the character set of the string by a binary number, where the i-th bit of the binary is 1 to indicate that the character set contains the i-th lowercase letter, and 0 to indicate that the character set does not contain the i-th lowercase letter.

Since strings containing repeated letters could not contribute to the formation of viable solutions, we traversed the ARR to filter out strings without repeated letters and added their corresponding binary numbers into an array, denoting them as masks.

Next, the backtracking method is used to solve this problem:

We use backtrack(pos,mask) to represent the recursive function, where POS represents the number of pos in the array masks that we are currently recursing, and mask represents the binary number of the string that we are currently connected to is mask.

For the number of pos, we have two methods: select or not select. If masks and masks have no common elements, then we can pick this number and call backtrack(pos+1,mask masks[pos]) to recurse. If we don’t pick this number, then we call backtrack(pos+1,mask) for recursion.

The length of the masks is n. When pos=n, calculate the number of 1 in the mask, which is the length of the feasible solution, and use it to update the maximum length of the feasible solution.

code

C++ code ‘ ‘C++ class Solution {public: int maxLength(vector &arr) {vector masks; for (string &s : arr) { int mask = 0; for (char ch : s) { ch -= ‘a’; If ((mask >> ch) &1) {// if (mask >> ch) &1) {// if (mask >> ch) &1) { break; } mask |= 1 << ch; } if (mask > 0) {masks. Push_back (mask); }}

int ans = 0; function<void(int, int)> backtrack = [&](int pos, int mask) { if (pos == masks.size()) { ans = max(ans, __builtin_popcount(mask)); return; } the if ((mask & masks (pos)) = = 0) {/ / mask and masks (pos) without the common elements backtrack (pos + 1, mask | masks (pos)); } backtrack(pos + 1, mask); }; backtrack(0, 0); return ans; }Copy the code

};

Copy the code