Maximum Length of a Concatenated String With Unique Characters

Medium Topics Company Tags

Choose a subsequence of arr and join its strings in their original order. Every letter in the joined string must occur at most once. Return the largest length you can obtain. You may choose no strings, giving length 0.

Example 1:

Input: arr = ["ab","bc","de"]

Output: 4

Explanation: Choose ab and de to obtain abde, whose four letters are distinct. Including bc with ab would repeat b, and including all three strings is therefore invalid.

Example 2:

Input: arr = ["aa","bb"]

Output: 0

Explanation: Both available strings already repeat a letter. Neither may be selected, so the best choice is the empty subsequence with length 0.

Example 3:

Input: arr = ["ab","cd","ef"]

Output: 6

Explanation: All six letters are different, so join all three strings to obtain abcdef with length 6.

Constraints:

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • Every string contains only lowercase English letters.


Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.