Frequencies of Shortest Supersequences
Frequencies of Shortest Supersequences is a hard dynamic programming problem solved with the bitmask dp pattern.
The best approach, optimal (subset dp for acyclic sets), runs in O(2^L · L + W) time and O(2^L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from enumerate doubled sets, check each with kahn's algorithm up.
Problem
You are given an array words of distinct two-letter strings. A common supersequence of words is a string that contains every word as a subsequence (the letters of the word appear in it in order, not necessarily next to each other). A shortest common supersequence is one of minimum length.
Find all shortest common supersequences, but treat two of them as the same if one is a rearrangement (permutation) of the other. Describe each distinct one by its letter frequencies: an array of 26 integers where index 0 counts 'a', index 1 counts 'b', and so on.
Return the list of these frequency arrays in any order.
Examples
Example 1
- Input
words = ["pq", "qp"]- Output
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]- Why
- One of p and q must appear twice, giving two shortest supersequences of length 3 that are not permutations of each other: "pqp" (p twice) and "qpq" (q twice).
Example 2
- Input
words = ["mn", "no", "mo"]- Output
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]- Why
- "mno" contains all three words as subsequences, and no letter needs repeating.
Example 3
- Input
words = ["zz", "zy"]- Output
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2]]- Why
- "zz" forces z to appear twice; "zzy" then covers "zy" too.
Constraints
1 <= words.length <= 256words[i].length == 2- All strings in
wordsare distinct. - All words together use at most 16 distinct lowercase letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Enumerate doubled sets, check each with Kahn's algorithm | O(2^L · (L + W)) | O(L + W) |
| Optimal (subset DP for acyclic sets) | O(2^L · L + W) | O(2^L) |
1Enumerate doubled sets, check each with Kahn's algorithm
O(2^L · (L + W))Each of the 2^L masks runs a topological sort over L letters and W words.O(L + W)In-degree counts and the edge list (output not counted).Number the distinct letters 0..L-1. For each subset of letters chosen to be single (the rest are doubled), run a topological sort on the edges between single letters. If all single letters can be ordered, the subset is feasible with length L + (number doubled). Keep the feasible subsets with the most single letters and turn each into a frequency array.
- Collect the distinct letters and map them to 0..L-1; turn each word into an edge.
- For every mask of single letters: count in-degrees over edges with both ends in the mask (a self-loop inside the mask makes it infeasible) and run Kahn's algorithm.
- If Kahn's algorithm removes every letter of the mask, the mask is feasible; track the largest feasible popcount.
- For each feasible mask with that popcount, output 1 for single letters, 2 for doubled letters, 0 for unused letters.
class Solution {
public List<List<Integer>> supersequences(String[] words) {
int[] id = new int[26];
Arrays.fill(id, -1);
List<Integer> letters = new ArrayList<>();
for (String w : words)
for (char ch : w.toCharArray())
if (id[ch - 'a'] < 0) { id[ch - 'a'] = letters.size(); letters.add(ch - 'a'); }
int L = letters.size();
int W = words.length;
int[] from = new int[W], to = new int[W];
for (int i = 0; i < W; i++) { from[i] = id[words[i].charAt(0) - 'a']; to[i] = id[words[i].charAt(1) - 'a']; }
int bestCount = -1;
List<Integer> bestMasks = new ArrayList<>();
for (int mask = 0; mask < (1 << L); mask++) {
int cnt = Integer.bitCount(mask);
if (cnt < bestCount) continue;
int[] indeg = new int[L];
boolean ok = true;
for (int i = 0; i < W && ok; i++) {
if ((mask >> from[i] & 1) == 1 && (mask >> to[i] & 1) == 1) {
if (from[i] == to[i]) ok = false;
else indeg[to[i]]++;
}
}
if (!ok) continue;
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < L; v++) if ((mask >> v & 1) == 1 && indeg[v] == 0) queue.add(v);
int removed = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
removed++;
for (int i = 0; i < W; i++)
if (from[i] == u && (mask >> to[i] & 1) == 1 && --indeg[to[i]] == 0) queue.add(to[i]);
}
if (removed != cnt) continue;
if (cnt > bestCount) { bestCount = cnt; bestMasks.clear(); }
bestMasks.add(mask);
}
List<List<Integer>> result = new ArrayList<>();
for (int mask : bestMasks) {
Integer[] freq = new Integer[26];
Arrays.fill(freq, 0);
for (int v = 0; v < L; v++) freq[letters.get(v)] = (mask >> v & 1) == 1 ? 1 : 2;
result.add(Arrays.asList(freq));
}
return result;
}
}class Solution:
def supersequences(self, words: List[str]) -> List[List[int]]:
idx = {}
letters = []
for w in words:
for ch in w:
if ch not in idx:
idx[ch] = len(letters)
letters.append(ord(ch) - 97)
L = len(letters)
edges = [(idx[w[0]], idx[w[1]]) for w in words]
best_count = -1
best_masks = []
for mask in range(1 << L):
cnt = bin(mask).count('1')
if cnt < best_count:
continue
indeg = [0] * L
ok = True
for a, b in edges:
if mask >> a & 1 and mask >> b & 1:
if a == b:
ok = False
break
indeg[b] += 1
if not ok:
continue
queue = deque(v for v in range(L) if mask >> v & 1 and indeg[v] == 0)
removed = 0
while queue:
u = queue.popleft()
removed += 1
for a, b in edges:
if a == u and mask >> b & 1:
indeg[b] -= 1
if indeg[b] == 0:
queue.append(b)
if removed != cnt:
continue
if cnt > best_count:
best_count = cnt
best_masks = []
best_masks.append(mask)
result = []
for mask in best_masks:
freq = [0] * 26
for v in range(L):
freq[letters[v]] = 1 if mask >> v & 1 else 2
result.append(freq)
return resultclass Solution {
public:
vector<vector<int>> supersequences(vector<string>& words) {
vector<int> id(26, -1), letters;
for (auto& w : words)
for (char ch : w)
if (id[ch - 'a'] < 0) { id[ch - 'a'] = letters.size(); letters.push_back(ch - 'a'); }
int L = letters.size(), W = words.size();
vector<int> from(W), to(W);
for (int i = 0; i < W; i++) { from[i] = id[words[i][0] - 'a']; to[i] = id[words[i][1] - 'a']; }
int bestCount = -1;
vector<int> bestMasks;
for (int mask = 0; mask < (1 << L); mask++) {
int cnt = __builtin_popcount(mask);
if (cnt < bestCount) continue;
vector<int> indeg(L, 0);
bool ok = true;
for (int i = 0; i < W && ok; i++) {
if ((mask >> from[i] & 1) && (mask >> to[i] & 1)) {
if (from[i] == to[i]) ok = false;
else indeg[to[i]]++;
}
}
if (!ok) continue;
deque<int> queue;
for (int v = 0; v < L; v++) if ((mask >> v & 1) && indeg[v] == 0) queue.push_back(v);
int removed = 0;
while (!queue.empty()) {
int u = queue.front();
queue.pop_front();
removed++;
for (int i = 0; i < W; i++)
if (from[i] == u && (mask >> to[i] & 1) && --indeg[to[i]] == 0) queue.push_back(to[i]);
}
if (removed != cnt) continue;
if (cnt > bestCount) { bestCount = cnt; bestMasks.clear(); }
bestMasks.push_back(mask);
}
vector<vector<int>> result;
for (int mask : bestMasks) {
vector<int> freq(26, 0);
for (int v = 0; v < L; v++) freq[letters[v]] = (mask >> v & 1) ? 1 : 2;
result.push_back(freq);
}
return result;
}
};function supersequences(words) {
const id = new Array(26).fill(-1), letters = [];
for (const w of words)
for (const ch of w) {
const c = ch.charCodeAt(0) - 97;
if (id[c] < 0) { id[c] = letters.length; letters.push(c); }
}
const L = letters.length, W = words.length;
const from = words.map((w) => id[w.charCodeAt(0) - 97]);
const to = words.map((w) => id[w.charCodeAt(1) - 97]);
const popcount = (x) => { let c = 0; while (x) { c += x & 1; x >>= 1; } return c; };
let bestCount = -1, bestMasks = [];
for (let mask = 0; mask < (1 << L); mask++) {
const cnt = popcount(mask);
if (cnt < bestCount) continue;
const indeg = new Array(L).fill(0);
let ok = true;
for (let i = 0; i < W && ok; i++) {
if ((mask >> from[i] & 1) && (mask >> to[i] & 1)) {
if (from[i] === to[i]) ok = false;
else indeg[to[i]]++;
}
}
if (!ok) continue;
const queue = [];
for (let v = 0; v < L; v++) if ((mask >> v & 1) && indeg[v] === 0) queue.push(v);
let removed = 0;
for (let h = 0; h < queue.length; h++) {
const u = queue[h];
removed++;
for (let i = 0; i < W; i++)
if (from[i] === u && (mask >> to[i] & 1) && --indeg[to[i]] === 0) queue.push(to[i]);
}
if (removed !== cnt) continue;
if (cnt > bestCount) { bestCount = cnt; bestMasks = []; }
bestMasks.push(mask);
}
return bestMasks.map((mask) => {
const freq = new Array(26).fill(0);
for (let v = 0; v < L; v++) freq[letters[v]] = (mask >> v & 1) ? 1 : 2;
return freq;
});
}2Optimal (subset DP for acyclic sets)
O(2^L · L + W)Each of the 2^L masks tries at most L candidate first letters, each check O(1) with bitmasks.O(2^L)One boolean per subset of letters.Instead of a fresh topological sort per subset, reuse smaller answers. A set of single letters can be ordered exactly when it contains a letter with no required predecessor inside the set (it goes first) and the rest of the set can be ordered. With pred[v] as a bitmask of letters that must come before v (v itself for a word like "vv"), ok[mask] = OR over v in mask of (pred[v] & mask) == 0 and ok[mask without v].
- Map letters to 0..L-1; for each word xy set bit x in pred[y].
- ok[0] = true. For mask = 1..2^L - 1: ok[mask] = true if some v in mask has (pred[v] & mask) == 0 and ok[mask ^ (1 << v)].
- Find the largest popcount among masks with ok[mask]; output a frequency array for every such mask (1 for single, 2 for doubled).
class Solution {
public List<List<Integer>> supersequences(String[] words) {
int[] id = new int[26];
Arrays.fill(id, -1);
List<Integer> letters = new ArrayList<>();
for (String w : words)
for (char ch : w.toCharArray())
if (id[ch - 'a'] < 0) { id[ch - 'a'] = letters.size(); letters.add(ch - 'a'); }
int L = letters.size();
int[] pred = new int[L];
for (String w : words) pred[id[w.charAt(1) - 'a']] |= 1 << id[w.charAt(0) - 'a'];
boolean[] ok = new boolean[1 << L];
ok[0] = true;
int bestCount = 0;
for (int mask = 1; mask < (1 << L); mask++) {
for (int v = 0; v < L; v++) {
if ((mask >> v & 1) == 1 && (pred[v] & mask) == 0 && ok[mask ^ (1 << v)]) {
ok[mask] = true;
break;
}
}
if (ok[mask]) bestCount = Math.max(bestCount, Integer.bitCount(mask));
}
List<List<Integer>> result = new ArrayList<>();
for (int mask = 0; mask < (1 << L); mask++) {
if (!ok[mask] || Integer.bitCount(mask) != bestCount) continue;
Integer[] freq = new Integer[26];
Arrays.fill(freq, 0);
for (int v = 0; v < L; v++) freq[letters.get(v)] = (mask >> v & 1) == 1 ? 1 : 2;
result.add(Arrays.asList(freq));
}
return result;
}
}class Solution:
def supersequences(self, words: List[str]) -> List[List[int]]:
idx = {}
letters = []
for w in words:
for ch in w:
if ch not in idx:
idx[ch] = len(letters)
letters.append(ord(ch) - 97)
L = len(letters)
pred = [0] * L
for w in words:
pred[idx[w[1]]] |= 1 << idx[w[0]]
full = 1 << L
ok = [False] * full
ok[0] = True
best_count = 0
for mask in range(1, full):
m = mask
while m:
low = m & -m
v = low.bit_length() - 1
if pred[v] & mask == 0 and ok[mask ^ low]:
ok[mask] = True
break
m ^= low
if ok[mask]:
best_count = max(best_count, bin(mask).count('1'))
result = []
for mask in range(full):
if not ok[mask] or bin(mask).count('1') != best_count:
continue
freq = [0] * 26
for v in range(L):
freq[letters[v]] = 1 if mask >> v & 1 else 2
result.append(freq)
return resultclass Solution {
public:
vector<vector<int>> supersequences(vector<string>& words) {
vector<int> id(26, -1), letters;
for (auto& w : words)
for (char ch : w)
if (id[ch - 'a'] < 0) { id[ch - 'a'] = letters.size(); letters.push_back(ch - 'a'); }
int L = letters.size();
vector<int> pred(L, 0);
for (auto& w : words) pred[id[w[1] - 'a']] |= 1 << id[w[0] - 'a'];
vector<char> ok(1 << L, 0);
ok[0] = 1;
int bestCount = 0;
for (int mask = 1; mask < (1 << L); mask++) {
for (int v = 0; v < L; v++) {
if ((mask >> v & 1) && (pred[v] & mask) == 0 && ok[mask ^ (1 << v)]) {
ok[mask] = 1;
break;
}
}
if (ok[mask]) bestCount = max(bestCount, __builtin_popcount(mask));
}
vector<vector<int>> result;
for (int mask = 0; mask < (1 << L); mask++) {
if (!ok[mask] || __builtin_popcount(mask) != bestCount) continue;
vector<int> freq(26, 0);
for (int v = 0; v < L; v++) freq[letters[v]] = (mask >> v & 1) ? 1 : 2;
result.push_back(freq);
}
return result;
}
};function supersequences(words) {
const id = new Array(26).fill(-1), letters = [];
for (const w of words)
for (const ch of w) {
const c = ch.charCodeAt(0) - 97;
if (id[c] < 0) { id[c] = letters.length; letters.push(c); }
}
const L = letters.length;
const pred = new Array(L).fill(0);
for (const w of words) pred[id[w.charCodeAt(1) - 97]] |= 1 << id[w.charCodeAt(0) - 97];
const full = 1 << L;
const ok = new Uint8Array(full);
const bits = new Uint8Array(full);
ok[0] = 1;
let bestCount = 0;
for (let mask = 1; mask < full; mask++) {
bits[mask] = bits[mask >> 1] + (mask & 1);
for (let v = 0; v < L; v++) {
if ((mask >> v & 1) && (pred[v] & mask) === 0 && ok[mask ^ (1 << v)]) {
ok[mask] = 1;
break;
}
}
if (ok[mask]) bestCount = Math.max(bestCount, bits[mask]);
}
const result = [];
for (let mask = 0; mask < full; mask++) {
if (!ok[mask] || bits[mask] !== bestCount) continue;
const freq = new Array(26).fill(0);
for (let v = 0; v < L; v++) freq[letters[v]] = (mask >> v & 1) ? 1 : 2;
result.push(freq);
}
return result;
}Edge cases to test
- A word with a repeated letter such as "aa" forces that letter to appear twice
- A cycle of order constraints ("ab", "bc", "ca") needs at least one doubled letter
- Several different minimal choices: all of them must be returned
- Letters that never occur get frequency 0
Hints
Hint 1
Every letter that occurs must appear at least once, and no letter ever needs more than two copies: put one copy at the very start and one at the very end and every word containing it is satisfied.
Hint 2
So a supersequence is described by the set D of doubled letters. The letters used once must be orderable so that every word xy among them has x before y. When is that possible?
Hint 3
It is possible exactly when the 'x before y' graph restricted to the single letters has no cycle (a word "xx" is a self-loop). Enumerate the at most 2^16 subsets, keep those that are acyclic, and return the ones with the fewest doubled letters.
FAQ
What is the best time complexity for Frequencies of Shortest Supersequences?
Optimal (subset DP for acyclic sets) runs in O(2^L · L + W) time and O(2^L) extra space. Each of the 2^L masks tries at most L candidate first letters, each check O(1) with bitmasks.
Which pattern does Frequencies of Shortest Supersequences use?
It is a dynamic programming problem that uses the bitmask dp pattern. Other problems with the same pattern: Optimal Account Balancing, Smallest Sufficient Team, Minimum Number of Work Sessions to Finish the Tasks.
Is there a brute force solution for Frequencies of Shortest Supersequences?
Yes. Enumerate doubled sets, check each with Kahn's algorithm takes O(2^L · (L + W)) time and O(L + W) space. Number the distinct letters 0..L-1.
Which edge cases should I test for Frequencies of Shortest Supersequences?
A word with a repeated letter such as "aa" forces that letter to appear twice; A cycle of order constraints ("ab", "bc", "ca") needs at least one doubled letter; Several different minimal choices: all of them must be returned; Letters that never occur get frequency 0.