Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

May 2026

Summary

Meta SWE coding round with a string manipulation problem. Pretty standard backtracking territory but the constraint around unique characters across concatenations is easy to fumble if you're not careful with how you track state.

Questions Asked (1)

Given an array of strings, select and concatenate any subset in any order such that the resulting string has all unique characters. Return the maximum possible length of such a string.

Algorithms & Data Structures

Author's notes

The example they give is almost too clean, 'un' + 'iq' = 'uniq', length 4.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model each string as a 26-bit mask of its characters, then use dynamic programming over subsets to find the maximum total length of concatenated strings with no overlapping bits. The DP state is the union mask, and we transition by adding a string if its mask doesn't intersect the current mask.

Pro tip: Mention that this is essentially a maximum weight independent set on a conflict graph, but the bitmask DP is efficient because the alphabet is small (26 bits). Also, note that strings with duplicate characters can be immediately discarded.

1. Preprocess strings

For each string, compute a 26-bit mask of its characters. If a string has duplicate characters, discard it because it can never be part of a valid concatenation.

2. Define DP state

Let dp[mask] be the maximum total length of a valid concatenation using a subset of strings whose combined character mask is exactly mask. Initialize dp[0] = 0 and all other states to -infinity.

3. Iterate and transition

For each string with mask s and length L, for each existing mask m where (m & s) == 0, update dp[m | s] = max(dp[m | s], dp[m] + L). Iterate over all strings and all masks.

4. Return result

The answer is the maximum value in the dp array, which represents the longest valid concatenation.

Key Points to Mention

Bitmask representation of character sets for efficient overlap checking.
Dynamic programming over subsets (state compression) to avoid exponential brute force.
Time complexity: O(N * 2^26) in the worst case, but practically much smaller due to constraints.
Space complexity: O(2^26) for the DP array, which is about 67 million entries (can be optimized with hashmap if sparse).
Handling of duplicate characters within a string: such strings are invalid and should be ignored.
The problem is equivalent to finding a maximum weight independent set in a conflict graph where edges represent character overlap.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.