LeetCode ~ 1239. The maximum length of a concatenated string

This is the fifth day of my participation in Gwen Challenge

1239. The maximum length of a concatenated string

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:

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. Input: arr = ["cha","r","act","ers"] Output: 6 Explanation: Possible solutions are "chaers" and "acters". Input: arr = [" abcdefghijklmnopqrstuvwxyz "] output: 26Copy the code

Tip:

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

Analysis of personal Ideas

Method 1: common backtracking

And they want any substring in the string array to be the longest string that has no repeating characters, so we need to basically filter string by string. Think of this, that basically did not run with backtracking, words do not say, directly open dry!

• Defines an array of characters and a variable that holds the maximum value
• Iterate over each bit of the string, summing up
• When the end of the array is reached, the maximum value is updated

class Solution {
    private int max;
    private int[] ch;
    public int maxLength(List<String> arr) {
        / / initialization
        max = 0;
        ch = new int[26];
        
        // Call the traceback method
        back(arr, 0.0);
        
        // Return the result
        return max;
    }

    /** * backtrace **@paramArr string array *@paramIndex Indicates the index pointer *@paramNumCount Indicates the total number of characters */
    public void back(List<String> arr, int index, int numCount){
        // The maximum value is updated
        if(index == arr.size()){
            max = Math.max(max, numCount);
        }

        for(int i = index; i < arr.size(); ++i){
            String s = arr.get(i);
            // Count the current string
            int count = add(s);
            
            / / recursion
            back(arr, i + 1, numCount + count);
            
            // Check whether the current string is in the bucket. If so, go back to the previous state
            if(0! = count){ remove(s,0, s.length()); }}}/** * Updates the characters in the string to the bucket **@paramS The character string */
    public int add(String s){
        int count = 0;
        char[] c = s.toCharArray();
        for(int i = 0; i < c.length; ++i){
            // If there are duplicate elements, delete the elements saved before the current location and end the loop
            if(ch[c[i] - 'a'] != 0){
                remove(s, 0, i);
                count = 0;
                break;
            }
            ++ch[c[i] - 'a'];
            ++count;
        }
        // Return the number of characters added.
        return count;
    }

    /** * Removes the element * from the bucket@paramS string *@paramStart Start boundary *@paramEnd End boundary */
    public void remove(String s, int start, int end){
        for(int i = start; i < end; ++i){
            --ch[s.charAt(i) - 'a']; }}}Copy the code

Submit the results

Method two: backtrack + bit operation

The official solution is very clear, here directly borrow, friends can go to the official website to view

Leetcode-cn.com/problems/ma…

class Solution {
    int ans = 0;

    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<Integer>();
        // Iterates through the string, eliminating any duplicate characters in a single string
        for (String s : arr) {
            int mask = 0;
            for (int i = 0; i < s.length(); ++i) {
                int ch = s.charAt(i) - 'a';
                
                // If the mask has ch, then s contains repeated letters and cannot form a feasible solution
                if (((mask >> ch) & 1) != 0) {
                    mask = 0;
                    break;
                }
                
                // add ch to mask
                mask |= 1 << ch; 
            }
            if (mask > 0) { masks.add(mask); }}/ / back
        backtrack(masks, 0.0);
        
        // Return the result
        return ans;
    }

    public void backtrack(List<Integer> masks, int pos, int mask) {
        // The maximum value is updated
        if (pos == masks.size()) {
            ans = Math.max(ans, Integer.bitCount(mask));
            return;
        }
        
        // Masks and masks[pos] have no common elements
        if ((mask & masks.get(pos)) == 0) { 
            backtrack(masks, pos + 1, mask | masks.get(pos));
        }
        backtrack(masks, pos + 1, mask); }}Copy the code

Complexity analysis

Time complexity: O(∣ σ ∣+ 2N). Space complexity: O(n).

Submit the results

leetcode-cn.com/problems/ma…