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

The title

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. Example 2:

Input: arr = [“cha”,”r”,”act”,”ers”] Output: 6 Explanation: Possible solutions are “chaers” and “acters”. Example 3:

Input: arr = [” abcdefghijklmnopqrstuvwxyz “] output: 26

Tip:

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • Arr [I] contains only lowercase letters

Their thinking

An operation

Because both the subsequence string arr and the concatenated string S need to be such that each character occurs only once, you can use a 32-bit integer to indicate the occurrence of 26 letters, with 1 for occurrence and 0 for non-occurrence.

The result of xor and addition operations can determine whether two strings have overlapping letters. Since addition and xor yield the same results for positive numbers without duplicate letters, if duplicate letters inevitably produce 1^1=0, 1+1=10, then addition and xor yield different results.

0 1 0 1 0 A 0 1 1 0 1 b For example, a+b is equal to 1 0 1 1 1 a^b is equal to 0 0 1 1 1 1Copy the code

backtracking

The current word can be added to the string by checking whether there are duplicate letters between the current word and the concatenated string

code

class Solution {
   int maxxx=0;
    public int maxLength(List<String> arr) {

        ArrayList<Integer> res = new ArrayList<>();
        for (String s : arr) {
            int cur=0,i=0;
            for (; i < s.length(); i++) {
                int c=1<<(s.charAt(i)-'a');
                if((c&cur)! =0) break;
                cur+=c;
            }
            if(i! =s.length())continue;
            res.add(cur);
        }
        backMaxLength(res,0.0);
        return maxxx;
    }

    public void backMaxLength(List<Integer> arr,int cur,int num) {

        if(cur==arr.size())
        {
            int sum=0;
           for (int i=0; i<26; i++) { sum+=(num&1);
               num>>=1;
           }
           maxxx= Math.max(maxxx,sum);
           return;
        }
        if((arr.get(cur)^num)==arr.get(cur)+num)
        {
              backMaxLength(arr,cur+1,arr.get(cur)+num);
        }
        backMaxLength(arr, cur+1, num); }}Copy the code