Maximum Length of a Concatenated String with Unique Characters

Maximum Length of a Concatenated String with Unique Characters - 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.

Input & Output

Example 1 — Basic Concatenation

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

› Output: 4

💡 Note: We can concatenate "un" + "iq" = "uniq" which has 4 unique characters. Other combinations like "unue" have duplicate 'u', so length 4 is maximum.

Example 2 — All Single Characters

$ Input: arr = ["cha","r","act","ers"]

› Output: 6

💡 Note: We can concatenate "cha" + "r" + "t" (from "act") is not valid since we must take whole strings. Best combination is "cha" + "ers" = "chaers" but has duplicate 'a'. Actually "r" + "act" = "ract" (5 chars) or "cha" + "r" = "char" (4 chars). Wait, we take whole strings: "r" + "act" = "ract" has unique chars, length 4.

Example 3 — No Valid Combination

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

› Output: 0

💡 Note: Each string itself contains duplicate characters ("aa" has two 'a's, "bb" has two 'b's), so we cannot use any string. Maximum length is 0.

Constraints

1 ≤ arr.length ≤ 16
1 ≤ arr[i].length ≤ 26
arr[i] contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings: ["un", "iq", "ue"]

Process

Find valid subsequence combinations with unique chars

Output

Maximum possible length: 4 from "uniq"

Key Takeaway

🎯 Key Insight: Use backtracking to explore all valid subsequence combinations while efficiently checking character uniqueness with bitmasks

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

This problem requires finding the longest concatenated string with unique characters from a subsequence of the input array. The key insight is to use backtracking to explore valid combinations while pruning invalid paths early. Best approach is backtracking with bit manipulation for O(1) character overlap detection. Time: O(2^n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(n × 2^n × k)	O(k)	Generate all possible subsequences and check each for unique characters
Bit Manipulation with Character Sets	O(2^n)	O(n)	Use bitmasks to represent character sets for efficient uniqueness checking
Backtracking with Pruning	O(2^n × k)	O(n × k)	Use recursive backtracking to build valid concatenations with early pruning

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all possible subsequences using bit manipulation (2^n combinations)
For each subsequence, concatenate all strings together
Check if the concatenated string has all unique characters
Track the maximum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n subsequences using bit masks

Concatenate

Join strings in each subsequence

Check

Verify unique characters and track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int hasUniqueChars(char* str) {
    int seen[256] = {0};
    for (int i = 0; str[i]; i++) {
        if (seen[(int)str[i]]) return 0;
        seen[(int)str[i]] = 1;
    }
    return 1;
}

int solution(char arr[][20], int n) {
    int maxLen = 0;
    
    // Generate all 2^n subsequences
    for (int mask = 0; mask < (1 << n); mask++) {
        char concat[1000] = "";
        // Build concatenated string for this subsequence
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                strcat(concat, arr[i]);
            }
        }
        
        // Check if all characters are unique
        int len = strlen(concat);
        if (hasUniqueChars(concat)) {
            if (len > maxLen) {
                maxLen = len;
            }
        }
    }
    
    return maxLen;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    char arr[16][20];
    int n = 0;
    
    char* token = strtok(line, "[],\"");
    while (token != NULL && n < 16) {
        if (strlen(token) > 0 && strcmp(token, "\n") != 0) {
            strcpy(arr[n++], token);
        }
        token = strtok(NULL, "[],\"");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2^n × k)

2^n subsequences, each taking O(n×k) to process where k is average string length

⚠ Quadratic Growth

Space Complexity

O(k)

Space for concatenated string of length k

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler