LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters Solution in Java, C++, Python & More | Explanation + Code

Description

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.

Solutions

Solution 1: State Compression + Bit Manipulation

Since the problem requires that the characters in the subsequence must not be repeated and all characters are lowercase letters, we can use a binary integer of length 26 to represent a subsequence. The i-th bit being 1 indicates that the subsequence contains the i-th character, and 0 indicates that it does not contain the i-th character.

We can use an array s to store the states of all subsequences that meet the conditions. Initially, s contains only one element 0.

Then we traverse the array arr. For each string t, we use an integer x to represent the state of t. Then we traverse the array s. For each state y, if x and y have no common characters, we add the union of x and y to s and update the answer.

Finally, we return the answer.

The time complexity is O(2ⁿ + L), and the space complexity is O(2ⁿ). Here, n is the length of the string array, and L is the sum of the lengths of all strings in the array.

PythonJavaC++GoTypeScript

class Solution: def maxLength(self, arr: List[str]) -> int: s = [0] for t in arr: x = 0 for b in map(lambda c: ord(c) - 97, t): if x >> b & 1: x = 0 break x |= 1 << b if x: s.extend((x | y) for y in s if (x & y) == 0) return max(x.bit_count() for x in s)(code-box)

class Solution { public int maxLength(List<String> arr) { List<Integer> s = new ArrayList<>(); s.add(0); int ans = 0; for (var t : arr) { int x = 0; for (char c : t.toCharArray()) { int b = c - 'a'; if ((x >> b & 1) == 1) { x = 0; break; } x |= 1 << b; } if (x > 0) { for (int i = s.size() - 1; i >= 0; --i) { int y = s.get(i); if ((x & y) == 0) { s.add(x | y); ans = Math.max(ans, Integer.bitCount(x | y)); } } } } return ans; } }(code-box)

class Solution { public: int maxLength(vector<string>& arr) { vector<int> s = {0}; int ans = 0; for (const string& t : arr) { int x = 0; for (char c : t) { int b = c - 'a'; if ((x >> b & 1) == 1) { x = 0; break; } x |= 1 << b; } if (x > 0) { for (int i = s.size() - 1; i >= 0; --i) { int y = s[i]; if ((x & y) == 0) { s.push_back(x | y); ans = max(ans, __builtin_popcount(x | y)); } } } } return ans; } };(code-box)

func maxLength(arr []string) (ans int) { s := []int{0} for _, t := range arr { x := 0 for _, c := range t { b := int(c - 'a') if (x>>b)&1 == 1 { x = 0 break } x |= 1 << b } if x > 0 { for i := len(s) - 1; i >= 0; i-- { y := s[i] if (x & y) == 0 { s = append(s, x|y) ans = max(ans, bits.OnesCount(uint(x|y))) } } } } return ans }(code-box)

function maxLength(arr: string[]): number { const s: number[] = [0]; let ans = 0; for (const t of arr) { let x = 0; for (const c of t) { const b = c.charCodeAt(0) - 97; if ((x >> b) & 1) { x = 0; break; } x |= 1 << b; } if (x > 0) { for (let i = s.length - 1; ~i; --i) { const y = s[i]; if ((x & y) === 0) { s.push(x | y); ans = Math.max(ans, bitCount(x | y)); } } } } return ans; } function bitCount(i: number): number { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }(code-box)