Problem

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

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3
4

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 <= 256
  • words[i].length == 2
  • All strings in words will altogether be composed of no more than 16 unique lowercase letters.
  • All strings in words are unique.

Examples

Solution

Method 1 – BFS with State Compression and Topological Search

Intuition

The shortest common supersequence (SCS) problem can be modeled as finding all minimal-length strings that contain all words as subsequences. We can use BFS to explore all possible supersequences, using state compression (bitmask) to avoid redundant work, and topological search to ensure all orderings are considered. For each unique SCS, we count the frequency of each letter.

Approach

  1. Use BFS to build SCSs by appending characters from any word that matches the current position.
  2. Represent the state as a tuple of current indices in each word and the current supersequence.
  3. Use a set to avoid revisiting the same state.
  4. Stop BFS when the shortest length is reached for all possible SCSs.
  5. For each unique SCS, count the frequency of each letter and add to the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def scsFrequencies(self, words: list[str]) -> list[list[int]]:
        from collections import deque, Counter
        n = len(words)
        lens = [len(w) for w in words]
        start = tuple([0]*n)
        queue = deque([(start, "")])
        seen = {start: ""}
        min_len = float('inf')
        res = set()
        while queue:
            state, s = queue.popleft()
            if all(state[i] == lens[i] for i in range(n)):
                if len(s) < min_len:
                    min_len = len(s)
                    res = {s}
                elif len(s) == min_len:
                    res.add(s)
                continue
            if len(s) > min_len:
                continue
            next_chars = set()
            for i in range(n):
                if state[i] < lens[i]:
                    next_chars.add(words[i][state[i]])
            for c in next_chars:
                new_state = list(state)
                for i in range(n):
                    if state[i] < lens[i] and words[i][state[i]] == c:
                        new_state[i] += 1
                new_state_t = tuple(new_state)
                if new_state_t not in seen or len(seen[new_state_t]) > len(s) + 1:
                    seen[new_state_t] = s + c
                    queue.append((new_state_t, s + c))
        ans = []
        for s in res:
            freq = [0]*26
            for ch in s:
                freq[ord(ch)-ord('a')] += 1
            ans.append(freq)
        return ans
 
1

// Due to the complexity and state explosion, a full Go implementation is omitted for brevity. The approach is similar: use BFS with a tuple of indices and a string, and a map for visited states.
1

// Due to the complexity and state explosion, a full Java implementation is omitted for brevity. The approach is similar: use BFS with a tuple of indices and a string, and a map for visited states.
1

// Due to the complexity and state explosion, a full Kotlin implementation is omitted for brevity. The approach is similar: use BFS with a tuple of indices and a string, and a map for visited states.
1

// Due to the complexity and state explosion, a full Rust implementation is omitted for brevity. The approach is similar: use BFS with a tuple of indices and a string, and a map for visited states.

1

// Due to the complexity and state explosion, a full TypeScript implementation is omitted for brevity. The approach is similar: use BFS with a tuple of indices and a string, and a map for visited states.

Complexity

  • ⏰ Time complexity: O(k^n * L) where k is the alphabet size, n is the number of words, and L is the SCS length. The number of states grows exponentially with the number of words.
  • 🧺 Space complexity: O(k^n * L) for storing all possible states and supersequences.