1239. Maximum Length of a Concatenated String with Unique Characters

Problem Statement

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.

Intuition

Approach:

For 26 characters maintain a mask ,
Also keep lenght in the remaining bits 

Now, in the early stages we eliminate aabc like strings to eliminate faltu branches

Links

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

Video Links

https://www.youtube.com/watch?v=FoqN_xSZ-Is&ab_channel=AryanMittal

Approach 1:

Bit Manipulation

C++

class Solution {
public:
    void wordBit(unordered_set<int> &st, string &str){
        int bit=0;
        for(auto &it: str){
            int temp = 1 << (it-'a');
            if(temp & bit)  return ;
            bit += temp; 
        }
        int len = str.size() << 26;
        st.insert(bit + len);
    }

    int find_ans(vector<int> &nums, int index, int mask){
        int oldMask = mask & ((1<<26) - 1);
        int oldLen = mask >> 26;
        int ans = oldLen;

        if(index >= nums.size())
            return ans;


        int newMask = nums[index] & ((1<<26) - 1);
        if(!(oldMask & newMask)){
            int newLen = nums[index] >> 26;
            int newMask = oldMask + newMask + ((newLen + oldLen) << 26);
            ans = max(ans, find_ans(nums, index+1, newMask));
        }

        ans = max(ans, find_ans(nums, index+1, mask));
        return ans;
    }

    int maxLength(vector<string>& arr) {
        unordered_set<int> st;
        for(auto &it: arr)
            wordBit(st, it);

        vector<int> nums(st.begin(), st.end());
        return find_ans(nums, 0, 0);
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems