Skip to main content

1239. Maximum Length of a Concatenated String with Unique Characters

medium

Given a list of strings, find the longest concatenation of a subset where all characters are unique. Backtracking with bitmask sets — every string becomes a 26-bit mask and intersection becomes an AND.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Skip any string that has internal duplicates — it can never be in a valid concatenation. Pre-filter those out and convert each remaining string to a 26-bit mask.

Hint 2

Backtrack from index 0 with a current combined mask. At each index, either skip or — if (currentMask & arr[i].mask) == 0 — include it (OR in the mask).

Hint 3

Maximize popcount(mask) across all explored paths.

Hint 4

Pruning: if remaining strings can't beat the current best, return. Small input (16) makes brute backtracking fine.

Solution approach

Reveal approach

Preprocess: for each string in arr, count chars. If any char repeats, skip it (can never be in a valid concatenation). Otherwise convert to a 26-bit mask. Backtrack(i, currentMask): if i == n, return popcount(currentMask). Option A (skip): backtrack(i + 1, currentMask). Option B (include, only if currentMask & masks[i] == 0): backtrack(i + 1, currentMask | masks[i]). Return max of the two. Time is O(2^n * n) where n is the count of usable strings (<= 16); the bit operations are O(1) per step which is the whole point of the mask representation.

Complexity

Time
O(2^n)
Space
O(n)

Related patterns

  • backtracking
  • bitmask
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google

Practice these live with InterviewChamp.AI

Drill Maximum Length of a Concatenated String with Unique Characters and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →