Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given an array of strings words. Find all shortest common supersequences (SCS) of words that are not permutations of each other.
A shortest common supersequence is a string of minimum length that contains each string in words as a subsequence.
Return a 2D array of integers freqs that represent all the SCSs. Each freqs[i] is an array of size 26, representing the frequency of each letter in the lowercase English alphabet for a single SCS. You may return the frequency arrays in any order.
Example 1:
Input: words = ["ab","ba"]
Output: [[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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
Explanation:
The two SCSs are "aba" and "bab". The output is the letter frequencies for each one.
Example 2:
Input: words = ["aa","ac"]
Output: [[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
Explanation:
The two SCSs are "aac" and "aca". Since they are permutations of each other, keep only "aac".
Example 3:
Input: words = ["aa","bb","cc"]
Output: [[2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
Explanation:
"aabbcc" and all its permutations are SCSs.
Constraints:
1 <= words.length <= 256words[i].length == 2words will altogether be composed of no more than 16 unique lowercase letters.words are unique.Problem summary: You are given an array of strings words. Find all shortest common supersequences (SCS) of words that are not permutations of each other. A shortest common supersequence is a string of minimum length that contains each string in words as a subsequence. Return a 2D array of integers freqs that represent all the SCSs. Each freqs[i] is an array of size 26, representing the frequency of each letter in the lowercase English alphabet for a single SCS. You may return the frequency arrays in any order.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Bit Manipulation · Topological Sort
["ab","ba"]
["aa","ac"]
["aa","bb","cc"]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3435: Frequencies of Shortest Supersequences
enum State { INIT, VISITING, VISITED }
class Solution {
public List<List<Integer>> supersequences(String[] words) {
List<List<Integer>> ans = new ArrayList<>();
List<int[]> edges = getEdges(words);
List<Integer> nodes = getNodes(edges);
int[] letterToIndex = getLetterToIndex(nodes);
List<Integer>[] graph = new List[nodes.size()];
for (int i = 0; i < nodes.size(); i++)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[letterToIndex[u]].add(letterToIndex[v]);
}
for (List<Integer> doubledSubset : getMinimumSubsets(graph)) {
int[] freq = new int[26];
for (final int letter : nodes)
freq[letter] = 1;
for (final int index : doubledSubset)
freq[nodes.get(index)] = 2;
ans.add(Arrays.stream(freq).boxed().collect(Collectors.toList()));
}
return ans;
}
// Returns a list of the minimum subsets of nodes that do not create a cycle
// when skipped.
private List<List<Integer>> getMinimumSubsets(List<Integer>[] graph) {
final int n = graph.length;
List<List<Integer>> res = new ArrayList<>();
for (int subsetSize = 0; subsetSize <= n; ++subsetSize) {
boolean[] combination = new boolean[n];
Arrays.fill(combination, n - subsetSize, n, true);
do {
List<Integer> doubledSubset = new ArrayList<>();
for (int i = 0; i < n; i++)
if (combination[i])
doubledSubset.add(i);
if (!hasCycleSkipping(graph, new HashSet<>(doubledSubset)))
res.add(doubledSubset);
} while (nextPermutation(combination));
if (!res.isEmpty())
return res;
}
return res;
}
// Returns true if there is a cycle in the `graph` when skipping any edges
// whose both endpoints are in `doubledSubset`.
private boolean hasCycleSkipping(List<Integer>[] graph, Set<Integer> doubledSubset) {
State[] states = new State[graph.length];
for (int i = 0; i < graph.length; ++i)
if (hasCycle(graph, i, states, doubledSubset))
return true;
return false;
}
private boolean hasCycle(List<Integer>[] graph, int u, State[] states,
Set<Integer> doubledSubset) {
if (states[u] == State.VISITING)
return true;
if (states[u] == State.VISITED)
return false;
states[u] = State.VISITING;
if (!doubledSubset.contains(u))
for (final int v : graph[u])
if (!doubledSubset.contains(v) && hasCycle(graph, v, states, doubledSubset))
return true;
states[u] = State.VISITED;
return false;
}
private List<int[]> getEdges(String[] words) {
List<int[]> edges = new ArrayList<>();
for (final String word : words)
edges.add(new int[] {word.charAt(0) - 'a', word.charAt(1) - 'a'});
return edges;
}
private List<Integer> getNodes(List<int[]> edges) {
TreeSet<Integer> nodes = new TreeSet<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
nodes.add(u);
nodes.add(v);
}
return new ArrayList<>(nodes);
}
private int[] getLetterToIndex(List<Integer> nodes) {
int[] letterToIndex = new int[26];
for (int i = 0; i < nodes.size(); ++i)
letterToIndex[nodes.get(i)] = i;
return letterToIndex;
}
private boolean nextPermutation(boolean[] arr) {
final int n = arr.length;
// From back to front, find the first false followed by true
int i;
for (i = n - 2; i >= 0; --i)
if (!arr[i] && arr[i + 1])
break;
// If no such pair found, we've reached the last permutation
if (i < 0)
return false;
// From back to front, find the first true to swap with arr[i].
for (int j = n - 1; j > i; --j)
if (arr[j] && !arr[i]) {
swap(arr, i, j);
break;
}
// Reverse arr[i + 1..n - 1].
reverse(arr, i + 1, n - 1);
return true;
}
private void reverse(boolean[] arr, int l, int r) {
while (l < r)
swap(arr, l++, r--);
}
private void swap(boolean[] arr, int i, int j) {
boolean temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Accepted solution for LeetCode #3435: Frequencies of Shortest Supersequences
package main
import (
"math/bits"
)
// https://space.bilibili.com/206214
func supersequences(words []string) [][]int {
// 收集有哪些字母，同时建图
all, mask2 := 0, 0
g := [26][]int{}
for _, s := range words {
x, y := int(s[0]-'a'), int(s[1]-'a')
all |= 1<<x | 1<<y
if x == y {
mask2 |= 1 << x
}
g[x] = append(g[x], y)
}
// 判断是否有环
hasCycle := func(sub int) bool {
color := [26]int8{}
var dfs func(int) bool
dfs = func(x int) bool {
color[x] = 1
for _, y := range g[x] {
// 只遍历在 sub 中的字母
if sub>>y&1 == 0 {
continue
}
if color[y] == 1 || color[y] == 0 && dfs(y) {
return true
}
}
color[x] = 2
return false
}
for i, c := range color {
// 只遍历在 sub 中的字母
if c == 0 && sub>>i&1 > 0 && dfs(i) {
return true
}
}
return false
}
set := map[int]struct{}{}
maxSize := 0
mask1 := all ^ mask2
// 枚举 mask1 的所有子集 sub
for sub, ok := mask1, true; ok; ok = sub != mask1 {
size := bits.OnesCount(uint(sub))
// 剪枝：如果 size < maxSize 就不需要判断了
if size >= maxSize && !hasCycle(sub) {
if size > maxSize {
maxSize = size
clear(set)
}
set[sub] = struct{}{}
}
sub = (sub - 1) & mask1
}
ans := make([][]int, 0, len(set)) // 预分配空间
for sub := range set {
cnt := make([]int, 26)
for i := range cnt {
cnt[i] = all>>i&1 + (all^sub)>>i&1
}
ans = append(ans, cnt)
}
return ans
}
func supersequences2(words []string) (ans [][]int) {
// 收集有哪些字母，同时建图
all := 0
g := [26][]int{}
for _, s := range words {
x, y := int(s[0]-'a'), int(s[1]-'a')
all |= 1<<x | 1<<y
g[x] = append(g[x], y)
}
// 判断是否有环
hasCycle := func(sub int) bool {
color := [26]int8{}
var dfs func(int) bool
dfs = func(x int) bool {
color[x] = 1
for _, y := range g[x] {
// 只遍历不在 sub 中的字母
if sub>>y&1 > 0 {
continue
}
if color[y] == 1 || color[y] == 0 && dfs(y) {
return true
}
}
color[x] = 2
return false
}
for i, c := range color {
// 只遍历不在 sub 中的字母
if c == 0 && sub>>i&1 == 0 && dfs(i) {
return true
}
}
return false
}
// 快速跳转到下一个要枚举的字母
nxt := [27]int{26: 26}
for i := 25; i >= 0; i-- {
if all>>i&1 > 0 {
nxt[i] = i
} else {
nxt[i] = nxt[i+1]
}
}
type pair struct{ i, sub int }
q := []pair{{nxt[0], 0}}
for {
for _, p := range q {
if !hasCycle(p.sub) {
cnt := make([]int, 26)
for i := range cnt {
cnt[i] = all>>i&1 + p.sub>>i&1
}
ans = append(ans, cnt)
}
}
if ans != nil {
return
}
tmp := q
q = nil
for _, p := range tmp {
for j := p.i; j < 26; j = nxt[j+1] {
q = append(q, pair{nxt[j+1], p.sub | 1<<j})
}
}
}
}
# Accepted solution for LeetCode #3435: Frequencies of Shortest Supersequences
from enum import Enum
class State(Enum):
INIT = 0
VISITING = 1
VISITED = 2
class Solution:
def supersequences(self, words: list[str]) -> list[list[int]]:
ans = []
edges = [(string.ascii_lowercase.index(words[0]),
string.ascii_lowercase.index(words[1]))
for words in words]
nodes = sorted({u for u, _ in edges} | {v for _, v in edges})
letterToIndex = {letter: i for i, letter in enumerate(nodes)}
graph = [[] for _ in range(len(nodes))]
for u, v in edges:
graph[letterToIndex[u]].append(letterToIndex[v])
for doubledSubset in self._getMinimumSubsets(graph):
freq = [0] * 26
for letter in nodes:
freq[letter] = 1
for index in doubledSubset:
freq[nodes[index]] = 2
ans.append(freq)
return ans
def _getMinimumSubsets(self, graph: list[list[int]]) -> list[tuple[int]]:
"""
Returns a list of the minimum subsets of nodes that do not create a cycle
when skipped.
"""
n = len(graph)
for subsetSize in range(n + 1):
doubleSubsets = []
for doubledSubset in itertools.combinations(range(n), subsetSize):
if not self._hasCycleSkipping(graph, set(doubledSubset)):
doubleSubsets.append(doubledSubset)
if doubleSubsets:
return doubleSubsets
return []
def _hasCycleSkipping(
self,
graph: list[list[int]],
doubledSubset: set[int]
) -> bool:
"""
Returns True if there is a cycle in the `graph` when skipping any edges
whose both endpoints are in `doubledSubset`.
"""
states = [State.INIT] * len(graph)
def hasCycle(u: int) -> bool:
if states[u] == State.VISITING:
return True
if states[u] == State.VISITED:
return False
states[u] = State.VISITING
if u not in doubledSubset:
for v in graph[u]:
if v in doubledSubset:
continue
if hasCycle(v):
return True
states[u] = State.VISITED
return False
return any(hasCycle(i) for i in range(len(graph)))
// Accepted solution for LeetCode #3435: Frequencies of Shortest Supersequences
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3435: Frequencies of Shortest Supersequences
// enum State { INIT, VISITING, VISITED }
//
// class Solution {
// public List<List<Integer>> supersequences(String[] words) {
// List<List<Integer>> ans = new ArrayList<>();
// List<int[]> edges = getEdges(words);
// List<Integer> nodes = getNodes(edges);
// int[] letterToIndex = getLetterToIndex(nodes);
// List<Integer>[] graph = new List[nodes.size()];
//
// for (int i = 0; i < nodes.size(); i++)
// graph[i] = new ArrayList<>();
//
// for (int[] edge : edges) {
// final int u = edge[0];
// final int v = edge[1];
// graph[letterToIndex[u]].add(letterToIndex[v]);
// }
//
// for (List<Integer> doubledSubset : getMinimumSubsets(graph)) {
// int[] freq = new int[26];
// for (final int letter : nodes)
// freq[letter] = 1;
// for (final int index : doubledSubset)
// freq[nodes.get(index)] = 2;
// ans.add(Arrays.stream(freq).boxed().collect(Collectors.toList()));
// }
//
// return ans;
// }
//
// // Returns a list of the minimum subsets of nodes that do not create a cycle
// // when skipped.
// private List<List<Integer>> getMinimumSubsets(List<Integer>[] graph) {
// final int n = graph.length;
// List<List<Integer>> res = new ArrayList<>();
//
// for (int subsetSize = 0; subsetSize <= n; ++subsetSize) {
// boolean[] combination = new boolean[n];
// Arrays.fill(combination, n - subsetSize, n, true);
// do {
// List<Integer> doubledSubset = new ArrayList<>();
// for (int i = 0; i < n; i++)
// if (combination[i])
// doubledSubset.add(i);
// if (!hasCycleSkipping(graph, new HashSet<>(doubledSubset)))
// res.add(doubledSubset);
// } while (nextPermutation(combination));
// if (!res.isEmpty())
// return res;
// }
// return res;
// }
//
// // Returns true if there is a cycle in the `graph` when skipping any edges
// // whose both endpoints are in `doubledSubset`.
// private boolean hasCycleSkipping(List<Integer>[] graph, Set<Integer> doubledSubset) {
// State[] states = new State[graph.length];
// for (int i = 0; i < graph.length; ++i)
// if (hasCycle(graph, i, states, doubledSubset))
// return true;
// return false;
// }
//
// private boolean hasCycle(List<Integer>[] graph, int u, State[] states,
// Set<Integer> doubledSubset) {
// if (states[u] == State.VISITING)
// return true;
// if (states[u] == State.VISITED)
// return false;
// states[u] = State.VISITING;
// if (!doubledSubset.contains(u))
// for (final int v : graph[u])
// if (!doubledSubset.contains(v) && hasCycle(graph, v, states, doubledSubset))
// return true;
// states[u] = State.VISITED;
// return false;
// }
//
// private List<int[]> getEdges(String[] words) {
// List<int[]> edges = new ArrayList<>();
// for (final String word : words)
// edges.add(new int[] {word.charAt(0) - 'a', word.charAt(1) - 'a'});
// return edges;
// }
//
// private List<Integer> getNodes(List<int[]> edges) {
// TreeSet<Integer> nodes = new TreeSet<>();
// for (int[] edge : edges) {
// final int u = edge[0];
// final int v = edge[1];
// nodes.add(u);
// nodes.add(v);
// }
// return new ArrayList<>(nodes);
// }
//
// private int[] getLetterToIndex(List<Integer> nodes) {
// int[] letterToIndex = new int[26];
// for (int i = 0; i < nodes.size(); ++i)
// letterToIndex[nodes.get(i)] = i;
// return letterToIndex;
// }
//
// private boolean nextPermutation(boolean[] arr) {
// final int n = arr.length;
//
// // From back to front, find the first false followed by true
// int i;
// for (i = n - 2; i >= 0; --i)
// if (!arr[i] && arr[i + 1])
// break;
//
// // If no such pair found, we've reached the last permutation
// if (i < 0)
// return false;
//
// // From back to front, find the first true to swap with arr[i].
// for (int j = n - 1; j > i; --j)
// if (arr[j] && !arr[i]) {
// swap(arr, i, j);
// break;
// }
//
// // Reverse arr[i + 1..n - 1].
// reverse(arr, i + 1, n - 1);
// return true;
// }
//
// private void reverse(boolean[] arr, int l, int r) {
// while (l < r)
// swap(arr, l++, r--);
// }
//
// private void swap(boolean[] arr, int i, int j) {
// boolean temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
// }
// Accepted solution for LeetCode #3435: Frequencies of Shortest Supersequences
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #3435: Frequencies of Shortest Supersequences
// enum State { INIT, VISITING, VISITED }
//
// class Solution {
// public List<List<Integer>> supersequences(String[] words) {
// List<List<Integer>> ans = new ArrayList<>();
// List<int[]> edges = getEdges(words);
// List<Integer> nodes = getNodes(edges);
// int[] letterToIndex = getLetterToIndex(nodes);
// List<Integer>[] graph = new List[nodes.size()];
//
// for (int i = 0; i < nodes.size(); i++)
// graph[i] = new ArrayList<>();
//
// for (int[] edge : edges) {
// final int u = edge[0];
// final int v = edge[1];
// graph[letterToIndex[u]].add(letterToIndex[v]);
// }
//
// for (List<Integer> doubledSubset : getMinimumSubsets(graph)) {
// int[] freq = new int[26];
// for (final int letter : nodes)
// freq[letter] = 1;
// for (final int index : doubledSubset)
// freq[nodes.get(index)] = 2;
// ans.add(Arrays.stream(freq).boxed().collect(Collectors.toList()));
// }
//
// return ans;
// }
//
// // Returns a list of the minimum subsets of nodes that do not create a cycle
// // when skipped.
// private List<List<Integer>> getMinimumSubsets(List<Integer>[] graph) {
// final int n = graph.length;
// List<List<Integer>> res = new ArrayList<>();
//
// for (int subsetSize = 0; subsetSize <= n; ++subsetSize) {
// boolean[] combination = new boolean[n];
// Arrays.fill(combination, n - subsetSize, n, true);
// do {
// List<Integer> doubledSubset = new ArrayList<>();
// for (int i = 0; i < n; i++)
// if (combination[i])
// doubledSubset.add(i);
// if (!hasCycleSkipping(graph, new HashSet<>(doubledSubset)))
// res.add(doubledSubset);
// } while (nextPermutation(combination));
// if (!res.isEmpty())
// return res;
// }
// return res;
// }
//
// // Returns true if there is a cycle in the `graph` when skipping any edges
// // whose both endpoints are in `doubledSubset`.
// private boolean hasCycleSkipping(List<Integer>[] graph, Set<Integer> doubledSubset) {
// State[] states = new State[graph.length];
// for (int i = 0; i < graph.length; ++i)
// if (hasCycle(graph, i, states, doubledSubset))
// return true;
// return false;
// }
//
// private boolean hasCycle(List<Integer>[] graph, int u, State[] states,
// Set<Integer> doubledSubset) {
// if (states[u] == State.VISITING)
// return true;
// if (states[u] == State.VISITED)
// return false;
// states[u] = State.VISITING;
// if (!doubledSubset.contains(u))
// for (final int v : graph[u])
// if (!doubledSubset.contains(v) && hasCycle(graph, v, states, doubledSubset))
// return true;
// states[u] = State.VISITED;
// return false;
// }
//
// private List<int[]> getEdges(String[] words) {
// List<int[]> edges = new ArrayList<>();
// for (final String word : words)
// edges.add(new int[] {word.charAt(0) - 'a', word.charAt(1) - 'a'});
// return edges;
// }
//
// private List<Integer> getNodes(List<int[]> edges) {
// TreeSet<Integer> nodes = new TreeSet<>();
// for (int[] edge : edges) {
// final int u = edge[0];
// final int v = edge[1];
// nodes.add(u);
// nodes.add(v);
// }
// return new ArrayList<>(nodes);
// }
//
// private int[] getLetterToIndex(List<Integer> nodes) {
// int[] letterToIndex = new int[26];
// for (int i = 0; i < nodes.size(); ++i)
// letterToIndex[nodes.get(i)] = i;
// return letterToIndex;
// }
//
// private boolean nextPermutation(boolean[] arr) {
// final int n = arr.length;
//
// // From back to front, find the first false followed by true
// int i;
// for (i = n - 2; i >= 0; --i)
// if (!arr[i] && arr[i + 1])
// break;
//
// // If no such pair found, we've reached the last permutation
// if (i < 0)
// return false;
//
// // From back to front, find the first true to swap with arr[i].
// for (int j = n - 1; j > i; --j)
// if (arr[j] && !arr[i]) {
// swap(arr, i, j);
// break;
// }
//
// // Reverse arr[i + 1..n - 1].
// reverse(arr, i + 1, n - 1);
// return true;
// }
//
// private void reverse(boolean[] arr, int l, int r) {
// while (l < r)
// swap(arr, l++, r--);
// }
//
// private void swap(boolean[] arr, int i, int j) {
// boolean temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.