Maximum Length of a Concatenated String with Unique Characters
Medium · Backtracking · Array · String · Backtracking · Bit Manipulation
Problem
You are given an array of strings arr. Choose some of its strings, keeping their original order, and join them into one string s. The choice is allowed only if no character appears twice in s.
Return the largest possible length of s. Choosing no strings at all gives length 0.
Examples
Input: arr = ["ab","cd","ace","ef"] Output: 6
Joining ab, cd and ef gives abcdef, with no letter twice.
Input: arr = ["aa","bc"] Output: 2
aa repeats a letter by itself, so only bc can be used.
Input: arr = ["xyz","yza","w"] Output: 4
xyz and yza share letters, so the best is one of them plus w.
Constraints
- 1 <= len(arr) <= 16
- 1 <= len(arr[i]) <= 26
- arr[i] contains only lowercase English letters
Approaches
- Baseline: join every subset and check it — time O(2^n · L), space O(L)
Follow-up
With many more strings, 2^n is out of reach, and the problem is a form of maximum-weight set packing, which is NP-hard. Exact solvers then add pruning: sort strings by length, and stop a branch when the letters used plus the letters still available cannot beat the best found.
Related problems
Start free on Cariara · Coding problems · System design studio
