← Meta Interview Insights

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

Intermediate
May 2026

Summary

Meta SWE coding round with a combinatorics/backtracking problem about selecting words to maximize unique characters. Pretty classic bitmask territory if you recognize it fast enough.

Questions Asked (1)

Q1

Given a list of words, select a subset such that when all chosen words are concatenated, no character appears more than once and the total number of distinct characters is maximized. Return any one such optimal subset.

Algorithms & Data Structures
Author's notes

The constraint that n <= 20 is basically a hint screaming bitmask DP at you.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model each word as a bitmask of its characters, discarding any word with duplicate characters. Then use dynamic programming over subsets of the 26-letter alphabet to find the maximum total characters achievable by combining disjoint masks, and reconstruct the chosen words.

Pro tip: Mention that you can prune the DP by only considering masks that are subsets of the current state, and that using a hash map for DP states can be more memory-efficient than a full array when the number of reachable states is small.

1. Preprocess words into bitmasks

For each word, compute a 26-bit integer where each bit represents a distinct character. If a word has any duplicate character, discard it immediately.

2. Define DP state and transition

Let dp[mask] store the maximum number of distinct characters achievable using a subset of words whose combined character set is exactly mask. Initialize dp[0] = 0 and others to -1. For each word mask w, update dp[new_mask] = max(dp[new_mask], dp[mask] + popcount(w)) for all masks disjoint from w.

3. Iterate and update DP

Process words one by one, updating the DP table in a way that avoids using the same word multiple times (e.g., iterate masks in descending order or use a new table per word).

4. Find optimal mask and reconstruct subset

After processing all words, find the mask with the maximum dp value. To reconstruct the chosen words, store parent pointers or backtrack by checking which word led to the optimal state.

5. Return any optimal subset

Output the list of words corresponding to the optimal mask. If multiple optimal subsets exist, any one is acceptable.

Key Points to Mention

  • Bitmask representation of character sets for efficient disjointness checks (using bitwise AND).
  • Dynamic programming over subsets of the alphabet (2^26 states) with state compression.
  • Handling words with duplicate characters by discarding them early.
  • Time complexity: O(N * 2^26) in the worst case, but often much faster with pruning.
  • Space complexity: O(2^26) for DP array, which is feasible (about 67 million entries) but can be optimized with a hash map.
  • Reconstruction of the chosen words using parent pointers or backtracking.

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