← DSA Atlas
Dedicated problem page · #1239

Maximum Length of Concatenated String with Unique Characters

MediumBit ManipulationBitmask subset searchBacktracking with bitmask representation of character sets
Solve on LeetCode ↗
1239
MediumBit ManipulationBacktracking with bitmask representation of character setsBitmask subset search

Maximum Length of Concatenated String with Unique Characters

Given an array of strings arr, form the longest possible concatenation of a subsequence of arr such that the concatenated string contains no repeated characters. Return that maximum length.

Open official problem prompt ↗
In plain English

Find the largest number of distinct letters obtainable by gluing together some chosen subset of the given strings.

Picture it like this

Think of each string as a Scrabble tile bearing a fixed set of letters. You may lay down tiles only if no letter repeats across everything on the board. You try combinations to maximize how many distinct letters end up on the board.

Example
Input
arr = ["un", "iq", "ue"]
Output
4
Why
Concatenating "un" + "iq" gives "uniq" (4 unique letters); "un" + "ue" repeats 'u' and is invalid, so 4 is the best.
Constraints
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i] contains only lowercase English letters
Pattern lesson

See the pattern, then code

Bitmask subset search
Recognition clue

Each string either fully joins the concatenation or is skipped, uniqueness matters, and the alphabet is just 26 letters — that maps a whole string to a 26-bit mask and turns 'no shared letters' into a bitwise-AND test.

↗
Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. Represent each usable string as a 26-bit set of its letters (discarding any string that already has internal duplicates). Two selections can be combined only if their masks share no bits (mask1 & mask2 == 0). Explore all compatible combinations, tracking the largest popcount reached.

New words, made simpleKnow these before the algorithm
Bitmask
A 26-bit integer where bit k is set if letter (a + k) is present.
Disjoint sets
Two masks with mask1 & mask2 == 0 share no letters and can be combined.
Popcount
The count of set bits, i.e. how many distinct letters a mask represents.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
String-based backtracking

Works but repeatedly rebuilds and rescans character sets.

Recurse over strings, keeping a running concatenation and re-checking uniqueness with a set each time.

Time O(2^n * L)Space O(L)
Best choiceBitmask combination

Uniqueness checks and merges become O(1) bit operations.

Convert each valid string to a 26-bit mask, then merge disjoint masks with OR and count bits.

Time O(2^n)Space O(2^n)
The rule we keep true

Invariant

The reachable list always contains exactly the masks of valid, internally-unique concatenations of strings considered so far; best equals the maximum popcount among them.

Why this is correct

Reasoning

A concatenation has all-unique characters iff the chosen strings' letter sets are pairwise disjoint, which the AND-is-zero test enforces at every merge. By expanding every existing reachable mask with each new compatible string, the search covers all valid subsets, so the maximum popcount found is optimal.

The algorithm in three movesSay these aloud before coding
1Precompute a bitmask for each string, skipping strings with internal repeats

masks: un={u,n}, iq={i,q}, ue={u,e}

2Maintain a growing list of reachable combined masks, starting with the empty mask 0

combine un|iq -> {u,n,i,q}, popcount 4

3For each string mask, try to OR it into every existing reachable mask that shares no bits, record the new mask, and update the best popcount

un|ue rejected (share 'u')

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
un0
iq1
ue2
1 · Readreachable = [0]
2 · AskWhat is the empty baseline?
3 · Update statebest = 0
4 · ResultEmpty concatenation has length 0
Key takeaway

Only masks with no overlapping bits can merge; un+iq reaches four unique letters.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-14Build a per-string mask

    Set one bit per letter; if a bit is already set the string has an internal duplicate and is skipped.

  2. 2
    Lines 15-21Expand reachable combinations

    For every previously reachable mask that shares no bit with the new one, record the merged mask and update the best popcount.

  3. 3
    Lines 22Return the maximum

    best holds the largest number of distinct letters achievable.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A string with internal duplicate letters (e.g. "aa") is discarded entirely
  • All strings mutually conflict, so the answer is the longest single valid string
  • arr with one string returns that string's unique-letter count (or 0 if it has repeats)
!

Common beginner mistakes

  • Forgetting to reject strings that already contain repeated characters before using them
  • Iterating reachable while appending to it without snapshotting, causing an ever-growing loop — copy with list(reachable)
  • Assuming you can always use every string; conflicts force a genuine subset search
Check your understanding

Why can uniqueness of a concatenation be reduced to a single AND operation between masks?

More in Bit Manipulation

#50Pow(x, n)Fast exponentiation (binary exponentiation)#89Gray CodeBinary-to-Gray transform (i XOR i>>1)#136Single NumberXOR cancellation#137Single Number IIBitwise finite-state counting (mod-3 per bit)#190Reverse BitsBit-by-bit reversal accumulation#191Number of 1 BitsBrian Kernighan bit clearing