LeetCode 3435 - Frequencies of Shortest Supersequences

LeetCode Problem 3435

Difficulty: 🔴 Hard
Topics: Array, String, Bit Manipulation, Graph Theory, Topological Sort, Enumeration

Solution

Problem Understanding

The problem asks us to find all shortest common supersequences (SCS) of a given list of two-character strings words. A shortest common supersequence is a string of minimum length that contains each word in words as a subsequence. Importantly, the output should not include SCSs that are permutations of each other; instead, it should return the letter frequency arrays for each unique SCS. Each frequency array is of size 26, corresponding to the lowercase English letters.

The input consists of up to 256 strings, each of length 2. The total set of characters across all strings is limited to 16 unique letters, which strongly suggests that a bitmask or combinatorial approach can be feasible because the effective search space is small. The output is a 2D list, where each inner list contains the counts of letters in one SCS.

Edge cases include:

• Words that share no characters, where the SCS is simply the concatenation of all words.
• Words that share characters, where overlapping reduces the length of the SCS.
• Situations where multiple SCSs have the same letter frequencies due to permutations, which should be deduplicated.

The constraints imply that although the number of words can be large, the total number of unique characters is small, allowing for graph-based or bitmask dynamic programming solutions. Each input string has length exactly two. Therefore every word imposes one of two possible constraints:

• If the word is "ab" with a != b, then any valid supersequence must contain an occurrence of a before an occurrence of b.
• If the word is "aa", then any valid supersequence must contain at least two occurrences of a.

The problem asks for all shortest common supersequences, but not as strings. Instead, we only need the frequency vector of each distinct multiset of letters. Two SCSs that are permutations of each other have identical frequency vectors, so only one frequency vector should be returned.

A crucial constraint is that all words together contain at most 16 distinct letters. Although there may be up to 256 words, the effective state space is determined by at most 16 vertices, which strongly suggests a bitmask solution.

The important observation is that every letter needs either one occurrence or two occurrences. No letter ever needs three or more occurrences because every constraint involves only a pair of letters.

The main edge cases are:

• Cycles such as "ab" and "ba", which force at least one duplicated letter.
• Larger directed cycles such as "ab", "bc", "ca".
• Self-loops such as "aa", which force that letter to appear twice.
• Independent components, where several different minimum solutions may exist.

Approaches

Brute Force

A naive approach would attempt to generate all possible orderings of the words and merge them into supersequences, checking each merged string for subsequence inclusion. After generating all supersequences, we would filter by minimum length and convert to frequency arrays while deduplicating permutations. This is correct but extremely inefficient because the number of permutations grows factorially with the number of words, and each merge operation requires scanning strings.

Optimal Approach

The key insight is that since each word is of length 2 and there are at most 16 unique letters, we can model the problem as a partial order graph. Each letter can be a node, and each word implies a directed edge from the first letter to the second. The problem then reduces to enumerating all topological sorts of this graph. Each topological sort gives a valid SCS with letters arranged respecting the order constraints. After computing all topological sorts, we convert each sort to a frequency array and deduplicate them based on letter counts.

This approach avoids generating all permutations of words directly and leverages the small alphabet size to keep the computational space manageable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((2n)!)	O(2n)	Generate all word merges and filter minimum-length supersequences. Too slow for n up to 256.
Optimal	O(2^k * k!)	O(2^k * k)	Build DAG from letter constraints, enumerate all topological sorts. k = number of unique letters (≤16).

Algorithm Walkthrough

1. Collect Unique Letters: Iterate over all words and collect all unique letters. Assign each letter an index for easier bitmask representation.
2. Build DAG: For each word, add a directed edge from the first character to the second. This encodes precedence constraints.
3. Compute In-Degrees: Track the number of incoming edges for each node. Nodes with zero in-degree can appear next in a topological sort.
4. Enumerate Topological Sorts: Recursively generate all topological orders of the graph using a backtracking approach. At each step, pick a node with zero in-degree, append it to the current order, decrease in-degrees of its neighbors, and recurse. After recursion, backtrack by restoring in-degrees and removing the node from the current order.
5. Convert to Frequencies: Each valid topological sort corresponds to an SCS. Count the occurrences of each letter to generate the 26-length frequency array.
6. Deduplicate Frequencies: Since permutations of letters with the same counts are considered the same, store frequency arrays in a set or hashable structure to remove duplicates.
7. Return Results: Convert unique frequency sets into a list and return.

Why it works: The topological sort ensures that all letter order constraints implied by the words are respected, guaranteeing that each word is a subsequence of any supersequence formed from a sort. Enumerating all valid topological sorts ensures we find all distinct SCSs. Deduplication by frequency ensures permutations are not counted multiple times. A direct approach would attempt to generate shortest common supersequences themselves.

One could view every word as a subsequence constraint and search over candidate strings, checking whether all constraints are satisfied. Even after restricting attention to shortest lengths, the number of possible strings grows exponentially with the number of letters and duplicated characters.

Since there can be up to 16 distinct letters, this approach is completely infeasible.

Key Insight

Construct a directed graph on the distinct letters.

For every word "ab" with a != b, add a directed edge a -> b.

For every word "aa", mark a as a letter that must appear twice.

Suppose we decide that a set D of letters will appear twice. Every other letter appears once.

A fundamental fact is:

A frequency assignment is feasible if and only if every directed cycle contains at least one duplicated letter.

Equivalently, after removing all duplicated letters, the remaining graph must be acyclic.

Therefore the problem becomes:

• Find all minimum-cardinality sets D that contain every mandatory duplicated letter coming from self-loops.
• After removing D, the remaining graph is a DAG.

This is exactly a minimum feedback vertex set problem on at most 16 vertices, which is small enough for complete subset enumeration.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential in supersequence length	Exponential	Enumerates candidate supersequences
Optimal	O(2^m · m²)	O(m)	Enumerates duplicated-letter sets, where m ≤ 16

Algorithm Walkthrough

Step 1: Collect the Relevant Letters

Extract all distinct letters appearing in the input.

Since the total number of distinct letters is at most 16, map them to indices 0..m-1.

Step 2: Build the Constraint Graph

For every word:

• If the two characters are different, add a directed edge.
• If the two characters are equal, mark that letter as mandatory duplicated.

Let mandatoryMask denote all letters forced to appear twice.

Step 3: Enumerate Candidate Duplication Sets

Every valid duplication set must contain mandatoryMask.

Let allMask = (1 << m) - 1.

Enumerate every subset D satisfying

mandatoryMask ⊆ D

The letters in D will have frequency 2.

All other letters will have frequency 1.

Step 4: Check Whether the Remaining Graph Is Acyclic

Let

R = allMask \ D

be the letters that appear only once.

The duplication set is feasible exactly when the graph induced by R is acyclic.

Perform a topological-removal test:

• Repeatedly remove vertices whose incoming edges from R are zero.
• If all vertices are removed, the graph is acyclic.
• Otherwise a cycle remains.

Step 5: Keep Only Minimum Solutions

Among all feasible duplication sets, compute the minimum size.

Only sets with this minimum size contribute shortest supersequences.

The resulting length is

m + |D|

because every duplicated letter contributes one extra occurrence.

Step 6: Build Frequency Vectors

For each minimum feasible duplication set:

• Frequency is 2 for letters in D.
• Frequency is 1 for all other used letters.
• Frequency is 0 for unused alphabet letters.

Store the resulting 26-element array.

Why it works

A duplicated letter can appear once before and once after any cycle involving that letter. Thus every cycle can be broken by duplicating at least one vertex on the cycle.

Conversely, if a cycle remains among letters that appear only once, those letters must occur in a cyclic ordering, which is impossible.

Therefore a duplication set is feasible exactly when its removal destroys all directed cycles. Minimizing the number of duplicated letters minimizes the supersequence length, and every minimum feasible duplication set yields one distinct frequency vector.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def supersequences(self, words: List[str]) -> List[List[int]]:
        letters = sorted(set(c for word in words for c in word))
        idx = {c: i for i, c in enumerate(letters)}
        n = len(letters)
        
        # Build graph
        graph = defaultdict(list)
        in_degree = [0] * n
        for word in words:
            u, v = idx[word[0]], idx[word[1]]
            graph[u].append(v)
            in_degree[v] += 1
        
        results = set()
        
        def backtrack(path, visited, in_deg):
            if len(path) == n:
                freq = [0] * 26
                for i in path:
                    freq[ord(letters[i]) - ord('a')] += 1
                results.add(tuple(freq))
                return
            for i in range(n):
                if not visited[i] and in_deg[i] == 0:
                    visited[i] = True
                    for nei in graph[i]:
                        in_deg[nei] -= 1
                    backtrack(path + [i], visited, in_deg)
                    for nei in graph[i]:
                        in_deg[nei] += 1
                    visited[i] = False
        
        visited = [False] * n
        backtrack([], visited, in_degree[:])
        return [list(freq) for freq in results]

The implementation first maps each unique letter to an index, constructs a graph representing order constraints, then uses backtracking to enumerate all topological sorts. Each sort is converted into a frequency array, and duplicates are eliminated via a set.

class Solution: def supersequences(self, words: List[str]) -> List[List[int]]: letters = sorted(set("".join(words))) m = len(letters)

    idx = {ch: i for i, ch in enumerate(letters)}

    pred = [0] * m
    mandatory_mask = 0

    for word in words:
        a = idx[word[0]]
        b = idx[word[1]]

        if a == b:
            mandatory_mask |= 1 << a
        else:
            pred[b] |= 1 << a

    all_mask = (1 << m) - 1

    def is_acyclic(remaining: int) -> bool:
        cur = remaining

        while cur:
            removable = 0

            temp = cur
            while temp:
                bit = temp & -temp
                v = bit.bit_length() - 1

                if (pred[v] & cur) == 0:
                    removable |= bit

                temp ^= bit

            if removable == 0:
                return False

            cur ^= removable

        return True

    best = m + 1
    answers = []

    free_mask = all_mask ^ mandatory_mask

    sub = free_mask
    while True:
        duplicate_mask = mandatory_mask | sub

        remaining = all_mask ^ duplicate_mask

        if is_acyclic(remaining):
            cnt = duplicate_mask.bit_count()

            if cnt < best:
                best = cnt
                answers = [duplicate_mask]
            elif cnt == best:
                answers.append(duplicate_mask)

        if sub == 0:
            break

        sub = (sub - 1) & free_mask

    result = []

    for mask in answers:
        freq = [0] * 26

        for ch in letters:
            freq[ord(ch) - ord('a')] = 1

        temp = mask
        while temp:
            bit = temp & -temp
            v = bit.bit_length() - 1
            freq[ord(letters[v]) - ord('a')] = 2
            temp ^= bit

        result.append(freq)

    return result

The implementation first compresses the used letters into indices `0..m-1`. The array `pred` stores incoming-edge bitmasks. A self-loop does not become a graph edge, instead it contributes to `mandatory_mask`.

The helper function `is_acyclic` performs a topological-removal process on a bitmask of remaining vertices. If at some point no vertex has zero in-degree within the current subgraph, a cycle exists.

All supersets of `mandatory_mask` are enumerated. For each candidate duplication set, the induced graph on nonduplicated letters is tested for acyclicity. The minimum feasible duplication count is recorded, and all minimum solutions are converted into frequency vectors.

## Go Solution

```go
package main

func supersequences(words []string) [][]int {
	lettersMap := make(map[byte]bool)
	for _, w := range words {
		lettersMap[w[0]] = true
		lettersMap[w[1]] = true
	}
	letters := make([]byte, 0, len(lettersMap))
	idx := make(map[byte]int)
	i := 0
	for c := range lettersMap {
		letters = append(letters, c)
		idx[c] = i
		i++
	}
	n := len(letters)
	graph := make([][]int, n)
	inDeg := make([]int, n)
	for _, w := range words {
		u, v := idx[w[0]], idx[w[1]]
		graph[u] = append(graph[u], v)
		inDeg[v]++
	}
	resultsMap := make(map[[26]int]bool)
	var backtrack func(path []int, visited []bool, inDeg []int)
	backtrack = func(path []int, visited []bool, inDeg []int) {
		if len(path) == n {
			var freq [26]int
			for _, i := range path {
				freq[letters[i]-'a']++
			}
			resultsMap[freq] = true
			return
		}
		for i := 0; i < n; i++ {
			if !visited[i] && inDeg[i] == 0 {
				visited[i] = true
				for _, nei := range graph[i] {
					inDeg[nei]--
				}
				backtrack(append(path, i), visited, inDeg)
				for _, nei := range graph[i] {
					inDeg[nei]++
				}
				visited[i] = false
			}
		}
	}
	visited := make([]bool, n)
	inDegCopy := make([]int, n)
	copy(inDegCopy, inDeg)
	backtrack([]int{}, visited, inDegCopy)
	result := make([][]int, 0, len(resultsMap))
	for freq := range resultsMap {
		temp := make([]int, 26)
		for i := 0; i < 26; i++ {
			temp[i] = freq[i]
		}
		result = append(result, temp)
	}
	return result
}

The Go solution mirrors the Python approach but carefully handles slices and fixed-size arrays for frequency storage. Go maps with array keys are used to deduplicate results efficiently.

Worked Examples

Example 1: words = ["ab","ba"]

1. Unique letters: ['a','b']
2. Graph edges: a -> b and b -> a
3. No valid linear order satisfies both, so topological sorts allow each letter to appear first, resulting in "aba" and "bab".
4. Frequency arrays: [1,2,...] and [2,1,...].

Example 2: words = ["aa","ac"]

1. Unique letters: ['a','c']
2. Graph edges: a -> a (ignored for SCS since repeated letters allowed) and a -> c
3. Only one valid frequency array: [2,0,1,...].

Example 3: words = ["aa","bb","cc"]

1. Unique letters: ['a','b','c']
2. No order constraints beyond single letters

import ( "math/bits" "sort" )

func supersequences(words []string) [][]int { letterSet := map[byte]bool{} for _, w := range words { letterSet[w[0]] = true letterSet[w[1]] = true }

letters := make([]byte, 0, len(letterSet))
for ch := range letterSet {
	letters = append(letters, ch)
}
sort.Slice(letters, func(i, j int) bool {
	return letters[i] < letters[j]
})

m := len(letters)

idx := make(map[byte]int)
for i, ch := range letters {
	idx[ch] = i
}

pred := make([]int, m)
mandatoryMask := 0

for _, w := range words {
	a := idx[w[0]]
	b := idx[w[1]]

	if a == b {
		mandatoryMask |= 1 << a
	} else {
		pred[b] |= 1 << a
	}
}

allMask := (1 << m) - 1

isAcyclic := func(remaining int) bool {
	cur := remaining

	for cur != 0 {
		removable := 0

		for v := 0; v < m; v++ {
			if (cur&(1<<v)) == 0 {
				continue
			}

			if (pred[v] & cur) == 0 {
				removable |= 1 << v
			}
		}

		if removable == 0 {
			return false
		}

		cur ^= removable
	}

	return true
}

best := m + 1
var masks []int

freeMask := allMask ^ mandatoryMask

for sub := freeMask; ; sub = (sub - 1) & freeMask {
	duplicateMask := mandatoryMask | sub
	remaining := allMask ^ duplicateMask

	if isAcyclic(remaining) {
		cnt := bits.OnesCount(uint(duplicateMask))

		if cnt < best {
			best = cnt
			masks = []int{duplicateMask}
		} else if cnt == best {
			masks = append(masks, duplicateMask)
		}
	}

	if sub == 0 {
		break
	}
}

ans := make([][]int, 0, len(masks))

for _, mask := range masks {
	freq := make([]int, 26)

	for _, ch := range letters {
		freq[int(ch-'a')] = 1
	}

	for v := 0; v < m; v++ {
		if (mask & (1 << v)) != 0 {
			freq[int(letters[v]-'a')] = 2
		}
	}

	ans = append(ans, freq)
}

return ans

}

The Go version follows the same logic as the Python implementation. The only notable differences are the use of `bits.OnesCount` for population counts and explicit integer bitmask manipulation instead of Python's built-in `bit_count()`.

## Worked Examples

### Example 1

Input:

["ab", "ba"]

Graph:

a -> b b -> a

| Candidate D | Remaining Vertices | Acyclic? |
| --- | --- | --- |
| {} | {a,b} | No |
| {a} | {b} | Yes |
| {b} | {a} | Yes |
| {a,b} | {} | Yes |

Minimum duplication count is 1.

Frequency vectors:

a twice, b once -> [2,1,...] a once, b twice -> [1,2,...]

### Example 2

Input:

["aa", "ac"]

Mandatory duplication:

D must contain a

Graph:

a -> c

| Candidate D | Remaining | Acyclic? |
| --- | --- | --- |
| {a} | {c} | Yes |
| {a,c} | {} | Yes |

Minimum duplication count is 1.

Frequency vector:

a = 2 c = 1

Result:

[2,0,1,...]

### Example 3

Input:

["aa", "bb", "cc"]

No ordering edges.

Mandatory duplication set:

{a,b,c}

Remaining graph is empty.

Only frequency vector:

a = 2 b = 2 c = 2

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(2^m · m²) | Enumerate all duplication subsets and perform DAG testing |
| Space | O(m) | Graph and bitmask storage |

Here `m` is the number of distinct letters, and the problem guarantees `m ≤ 16`. Therefore:

2^16 = 65536

which is easily manageable.

## Test Cases

```sql
s = Solution()

# Example 1
ans = s.supersequences(["ab", "ba"])
expected = {
    tuple([2,1] + [0]*24),
    tuple([1,2] + [0]*24),
}
assert {tuple(x) for x in ans} == expected  # 2-cycle

# Example 2
assert s.supersequences(["aa", "ac"]) == [
    [2,0,1] + [0]*23
]  # mandatory duplication

# Example 3
assert s.supersequences(["aa", "bb", "cc"]) == [
    [2,2,2] + [0]*23
]  # only self-loops

# Single edge
assert s.supersequences(["ab"]) == [
    [1,1] + [0]*24
]  # simple DAG

# 3-cycle
ans = s.supersequences(["ab", "bc", "ca"])
expected = {
    tuple([2,1,1] + [0]*23),
    tuple([1,2,1] + [0]*23),
    tuple([1,1,2] + [0]*23),
}
assert {tuple(x) for x in ans} == expected

# DAG chain
assert s.supersequences(["ab", "bc"]) == [
    [1,1,1] + [0]*23
]  # no duplication required

# Mandatory duplication plus cycle
ans = s.supersequences(["aa", "ab", "ba"])
assert ans == [
    [2,1] + [0]*24
]  # a already breaks cycle

# Disconnected cycles
ans = s.supersequences(["ab", "ba", "cd", "dc"])
assert len(ans) == 4  # choose one vertex from each cycle

Test Summary

Test	Why
["ab","ba"]	Smallest nontrivial cycle
["aa","ac"]	Mandatory duplicated letter
["aa","bb","cc"]	Only self-loops
["ab"]	Simple DAG
["ab","bc","ca"]	Directed 3-cycle
["ab","bc"]	No cycle present
["aa","ab","ba"]	Mandatory duplication already breaks cycle
["ab","ba","cd","dc"]	Multiple independent cycles

Edge Cases

Self-Loops

A word such as "aa" does not impose an ordering relation. Instead, it requires two occurrences of a. A common mistake is to insert a graph self-loop and treat it as a cycle to break later. The implementation handles this correctly by placing a directly into mandatory_mask.

Cycles of Length Greater Than Two

A cycle such as:

ab
bc
ca

cannot be resolved by topological ordering. At least one vertex must be duplicated. The implementation detects this because the induced graph on nonduplicated vertices fails the acyclicity test.

Multiple Independent Cycles

Consider:

ab, ba, cd, dc

There are two separate cycles. Breaking only one is insufficient. The algorithm examines every duplication set and keeps only those whose removal makes the entire remaining graph acyclic. Thus it correctly requires one duplicated letter from each cycle.

Already Acyclic Graphs

If the graph contains no cycles and there are no self-loops, the empty duplication set is feasible. The algorithm naturally discovers this and returns a single frequency vector with frequency one for every used letter.