Leetcode 1239. Maximum Length of a Concatenated String with Unique Characters

Problem Explanation:

The problem is asking to find the maximum length of a unique character string that can be formed by concatenating some of the strings from an array. Any string in the array could be used at most once. The length of each string in the input array is between 1 and 26, and all the strings only contain lowercase English letters. The task is to return the maximum possible length of the concatenated string with unique characters.

For instance, if the input array is ["un","iq","ue"], the possible concatenations are "","un","iq","ue","uniq" and "ique". The maximum length is 4.

The provided solution uses a depth-first search (DFS) approach in combination with bitwise operations. It applies bitwise operations to not only check for the duplicates within a string but also check for duplicates between concatenated strings.

Let's walk through step by step process using the same example

["un","iq","ue"]

• First, encode each string into an integer where each bit presents a unique character in a string. For example, encode 'un' into 11000000000000000000000000, 'iq' into 01001000000000000000000000, and 'ue' into 10001000000000000000000000.

• Now, maintain a list of all possible unique character combinations, initially it only contains an empty string which means 0 (00000000000000000000000000).

• Then go through each string in the input list, check each combination from the list, if current string has no overlap with the combination, then add a new combination with current string.

• Keep track of maximum length of unique character combination.

• In the last, return the maximum length.

This approach ensures that we check all possible concatenations of the strings in the array while keeping every character unique.

Solution in Python:

1
2python
3class Solution:
4    def maxLength(self, arr):
5        masks = [0]
6        res = 0
7        
8        for s in arr:
9            mask = 0
10            for c in s:
11                if (mask >> (ord(c) - ord('a'))) & 1: 
12                    # duplicate characters in the current string
13                    mask = 0
14                    break
15                mask |= 1 << (ord(c) - ord('a')) 
16            if mask == 0:  
17                # if there are duplicates in the current string, skip it
18                continue    
19            
20            new_masks = []
21            
22            for usedMask in masks:
23                if usedMask & mask:
24                    # if 's' conflicts with used, skip
25                    continue
26                # add a new mask 'mask + used' as a possible candidate
27                new_masks.append(usedMask | mask)
28                res = max(res, bin(usedMask | mask).count('1'))
29            
30            masks.extend(new_masks)
31
32        return res

Solution in Java:

1
2java
3class Solution {
4    public int maxLength(List<String> arr) {
5        List<Integer> masks = new ArrayList<>();
6        masks.add(0);
7        int res = 0;
8
9        for (String s : arr) {
10            int mask = 0;
11            for (char c : s.toCharArray()) {
12                if ((mask & (1 << (c - 'a'))) != 0) {
13                    mask = 0;
14                    break;
15                }
16                mask |= 1 << (c - 'a');
17            }
18            if (mask == 0)
19                continue;
20
21            List<Integer> newMasks = new ArrayList<>();
22            for (int usedMask : masks) {
23                if ((usedMask & mask) != 0)
24                    continue;
25                newMasks.add(usedMask | mask);
26                res = Math.max(res, Integer.bitCount(usedMask | mask));
27            }
28            masks.addAll(newMasks);
29        }
30
31        return res;
32    }
33}

Solution in JavaScript:

1
2javascript
3var maxLength = function(arr) {
4    let masks = [0];
5    let res = 0;
6    for(let s of arr) {
7        let mask = 0;
8        for(let c of s) {
9            if ((mask >> (c.charCodeAt(0) - 'a'.charCodeAt(0))) & 1) {
10                mask = 0;
11                break;
12            }
13            mask |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
14        }
15        if(mask === 0) continue;
16        let newMasks = [];
17        for(let usedMask of masks) {
18            if(usedMask & mask) continue;
19            newMasks.push(usedMask | mask);
20            res = Math.max(res, (usedMask | mask).toString(2).split('0').join('').length);
21        }
22        masks.push(...newMasks);
23    }
24    return res;
25};

Solution in C++:

1
2c++
3class Solution {
4public:
5    int maxLength(vector<string>& arr) {
6        vector<int> masks = {0};
7        int res = 0;
8        for (string s : arr) {
9            int mask = 0;
10            for (char c : s) {
11                if ((mask & (1 << (c - 'a'))) != 0) {
12                    mask = 0;
13                    break;
14                }
15                mask |= 1 << (c - 'a'); 
16            }
17            if (mask == 0) continue; 
18            vector<int> newMasks;
19            for (int used : masks) {
20                if ((used & mask) != 0) continue;
21                newMasks.push_back(used | mask);
22                res = max(res, __builtin_popcount(used | mask));
23            }
24            for (const int& mask : newMasks) masks.push_back(mask); 
25        }
26        return res;
27    }
28};

Solution in C#:

1
2CSharp
3public class Solution {
4    public int MaxLength(IList<string> arr) {
5        List<int> masks = new List<int>{0};
6        int res = 0;
7        foreach (string s in arr) {
8            int mask = 0;
9            foreach (char c in s) {
10                if ((mask & (1 << (c - 'a'))) != 0) {
11                    mask = 0;
12                    break;
13                }
14                mask |= 1 << (c - 'a');
15            }
16            if (mask == 0) 
17                continue;
18            List<int> newMasks = new List<int>();
19            foreach (int used in masks) {
20                if ((used & mask) != 0) 
21                    continue;
22                newMasks.Add(used | mask);
23                res = Math.Max(res, BitCount(used | mask));
24            }
25            masks.AddRange(newMasks);
26        }
27        return res;
28    }
29        public int BitCount(int n) {
30            int count = 0;
31            for (int i = 0; i < 32; i++) {
32                if ((n & 1) == 1) 
33                    count++;
34                n >>= 1;
35            }
36            return count;
37        }
38    }

In above examples, mask |= 1 << (c - 'a') is used to set the bit at the position (c - 'a') to 1. mask & (1 << (c - 'a')) is used to check whether the bit at the position (c - 'a') is 1 or not. If it's 1, then it means character 'c' is appearing for the second time and in this case break the loop nd set current mask as zero to skip this string. Thus we skip the strings having duplicate characters and strings conflicting with the combinations in the mask. This whole approach ensures that every character is unique in the final concatenated string.Using the bitwise mask, we're able to represent a string of up to 26 units in length, where each bit represents a unique character (e.g., the 1st bit for 'a', the 2nd for 'b', and so on). In other words, the bitset operations allow us to map a string to an integer in such a way that we can detect overlapping strings without needing to compare characters one by one.

When we concatenate two strings, it is the equivalent of an OR operation on their corresponding bitsets. To check if two strings overlap, we perform an AND operation which would produce a non-zero result if and only if there are common characters.

The drawback of the bitset approach lies in the limited number of available bits in a standard integer. If we had to work with larger sets of elements, we would need to switch to an alternative solution, such as a bitmask approach using more complex data structures or utilizing hashing techniques.

Another factor to consider is that bitwise operations can be slower on some platforms, and their performance varies greatly across different programming languages. Hence, they are most effective when applied to large sets of data in languages with native support for bitwise operations, such as C++ or Python.

In addition to bitwise operations, the problem can be solved using recursive backtracking, depth-first search or dynamic programming, which might lead to easier to understand code, but also higher time complexity. So, the most suitable strategy depends on the specific requirements of the problem at hand.

Hopefully, this article has helped you gain understanding of the described approach and will be useful when you are faced with similar problems.

Stay tuned for more tutorials and happy coding!