#1239

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Maximum Length of a Concatenated String with Unique Characters

Find the maximum length of a concatenated string from an array with all unique characters using backtracking search with pruning.

array string backtracking bit manipulation

Problem Statement

Given an array of strings arr, generate a string s by concatenating a subsequence of arr such that s contains only unique characters. Your task is to find the maximum possible length of s. Each string in arr consists of lowercase English letters, and a valid subsequence may skip elements without changing their order.

Return an integer representing the maximum length of a string formed by concatenating elements from any subsequence of arr with all distinct characters. Consider that some strings in arr may contain overlapping characters, so careful selection and pruning of subsequences is required to avoid duplicates.

Examples

Example 1

Input: arr = ["un","iq","ue"]

Output: 4

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

Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").

Example 3

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]

Output: 26

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.

Solution Approach

Backtracking with Bitmask

Use a backtracking search to explore all possible subsequences. Track used characters with a 26-bit integer mask. If adding a string would cause a duplicate, skip that branch, pruning unnecessary paths.

Pruning Invalid Combinations Early

Before concatenating a string, check if it contains duplicate characters or overlaps with the current mask. This reduces the number of recursive calls and ensures only valid unique-character strings are considered.

Compute Maximum Length Efficiently

During recursion, keep updating the maximum length encountered so far. At the end, return the largest length found. This approach leverages both backtracking and pruning to handle the exponential search space effectively.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(2^n * m) where n is arr.length and m is the average string length, due to exploring all subsequences with bitmask checks. Space complexity is O(n) for recursion stack, plus O(1) for bitmask storage.

What Interviewers Usually Probe

Does the candidate consider character uniqueness across combined strings?
Does the solution prune paths where duplicates would occur instead of exploring blindly?
Are bitmask techniques or efficient character tracking applied for faster checks?

Common Pitfalls or Variants

Common pitfalls

Not checking for duplicate characters inside individual strings before combining.
Failing to prune subsequences early, leading to timeouts on larger arrays.
Using string concatenation repeatedly instead of a bitmask or set, increasing runtime unnecessarily.

Follow-up variants

Find the maximum length where characters can repeat at most k times.
Return all possible concatenated strings with maximum length and unique characters.
Solve the problem when strings contain uppercase letters and digits as well.

FAQ

What is the main pattern used in Maximum Length of a Concatenated String with Unique Characters?

The core pattern is backtracking search with pruning, checking character uniqueness via a bitmask.

Can I use sets instead of bitmasks?

Yes, sets work for tracking used characters, but bitmasks are faster and use less memory.

How does pruning help in this problem?

Pruning stops recursion early when a string would introduce duplicate characters, saving exponential computations.

What is the maximum array length constraint?

The input array length is between 1 and 16, which allows backtracking without exceeding reasonable computation time.

Do I need to check for duplicates inside a single string?

Yes, strings with repeated characters cannot contribute to a valid unique-character concatenation.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

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)

Continue Practicing

#1255 maximum score words formed by letters #691 stickers to spell word #1178 number of valid words for each puzzle