# Frequencies of Shortest Supersequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/frequencies-of-shortest-supersequences)
Canonical: https://scaleengineer.com/dsa/problems/frequencies-of-shortest-supersequences
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, String, Graph
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## 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:**

**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 <= 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.

# Approaches
## Brute-Force Backtracking on Word Progress
A brute-force approach would be to explore all possible sequences of characters and check if they are valid supersequences. We can refine this by only adding characters that are needed to satisfy the next requirement for at least one word. This can be formulated as a backtracking or recursive search on the state space of satisfied words.
**Time:** O(|C| * 2^n * L) where `|C|` is the alphabet size, `n` is the number of words, and `L` is the length of the SCS. This is due to exploring `|C|` transitions from each of the `2^n` states. · **Space:** O(2^n * L) where `n` is the number of words and `L` is the length of SCS. This is for storing the memoization table and solution sets.
**Pros:** Conceptually simple and directly follows the problem definition.; Guaranteed to find the correct solution if it could run to completion.
**Cons:** The state space is `O(2^n)`, where `n` is the number of words. Given `n <= 256`, this is computationally infeasible.; The depth of the recursion can be large, potentially leading to a stack overflow for long supersequences.; Storing frequency maps for each state in the recursion can consume a large amount of memory.
### Explanation
This method models the problem as a shortest path problem on a state graph. A state is defined by a bitmask `pmask` of length `n`, where the `i`-th bit indicates whether we are waiting for the first (`0`) or second (`1`) character of `words[i]`. We use a recursive search with memoization (a form of dynamic programming) to explore this state space.

The search starts from an initial state where no characters have been placed and we need the first character of every word (`pmask = 0`). At any state, we can transition to a new state by appending a character `c`. This `c` must be the next required character for some word(s). Appending `c` updates `pmask` for all words that were waiting for it. We explore all such valid character choices.

The goal is to find the paths from the initial state to the final state (all words satisfied) that have the minimum length (number of characters appended). Because we need all shortest supersequences, a simple DP storing only the minimum length is not enough. We would need to store the set of frequency maps for all shortest paths to each state.

```java
// This is a conceptual illustration. A direct implementation is not feasible due to complexity.
class BruteForceApproach {
    // n = words.length
    // Map<Integer, Integer> memo = new HashMap<>(); // memo[pmask] -> minLength
    // Map<Integer, Set<int[]>> solutions = new HashMap<>(); // memo[pmask] -> set of frequency maps

    public void findSCS(int pmask, int[] currentFreqs, String[] words) {
        // Base case: all words satisfied
        if (pmask == (1 << words.length) - 1) {
            // Process the found supersequence's frequency map
            return;
        }

        // Pruning using memoization
        int currentLength = 0;
        for (int f : currentFreqs) currentLength += f;
        // if (memo.containsKey(pmask) && currentLength >= memo.get(pmask)) {
        //     return;
        // }

        // Find all possible next characters
        Set<Character> nextChars = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            int ptr = (pmask >> i) & 1;
            nextChars.add(words[i].charAt(ptr));
        }

        // Explore transitions
        for (char c : nextChars) {
            int nextPmask = pmask;
            for (int i = 0; i < words.length; i++) {
                int ptr = (pmask >> i) & 1;
                if (words[i].charAt(ptr) == c) {
                    nextPmask |= (1 << i);
                }
            }
            
            // Recursive call
            currentFreqs[c - 'a']++;
            findSCS(nextPmask, currentFreqs, words);
            // Backtrack
            currentFreqs[c - 'a']--;
        }
    }
}
```
This approach is primarily educational to understand the problem's complexity. The state space of `2^n` makes it impractical for the given constraints.
### Algorithm
This approach attempts to find the shortest common supersequences by exploring all possible valid sequences of characters using backtracking.
1.  Define a recursive function, say `findSCS(currentState)`, where the state includes:
    *   `pmask`: A bitmask of length `n` representing the progress for each word. `(pmask >> i) & 1` is 0 if we need the first character of `words[i]`, and 1 if we need the second.
    *   `freqMap`: The frequency map of characters in the sequence built so far.
2.  Use memoization, `memo[pmask]`, to store the shortest length found to reach state `pmask` to avoid recomputing for the same subproblem.
3.  The base case for the recursion is when all words are satisfied (`pmask` has all bits set to 1). At this point, we have found a valid supersequence. We compare its length with the minimum length found so far and update our set of solutions.
4.  In the recursive step, identify all possible next characters. A character `c` can be chosen if it's the next required character for at least one word.
5.  For each possible next character `c`:
    a.  Create a `newPmask` by advancing the pointers for all words that were waiting for `c`.
    b.  Increment the count of `c` in the `freqMap`.
    c.  Make a recursive call: `findSCS(newPmask, newFreqMap)`.
    d.  Backtrack by decrementing the count of `c`.
6.  The initial call would be `findSCS(0, new int[26])`.
7.  After the search completes, filter the collected solution frequency maps to keep only those that are not permutations of each other.

## SCC Decomposition and Combinatorial Construction
A much more efficient approach leverages the small number of unique characters (`|C| <= 16`). The problem can be modeled on a character dependency graph. Cycles in this graph correspond to conflicting ordering requirements that must be resolved by using multiple instances of characters. By analyzing the graph's structure, specifically its Strongly Connected Components (SCCs), we can determine the minimum number of characters required for a valid supersequence and systematically find all non-permutation-equivalent solutions.
**Time:** O(n + |C|^2 + N_sccs * N_sols * Comb), where `n` is for parsing, `|C|^2` for graph building and SCCs. The main work is iterating through solutions (`N_sols`) for each SCC (`N_sccs`) and generating combinations (`Comb`), which depends on `|S|` and `diff`. · **Space:** O(N_sols * |C| + n + |C|^2), where `N_sols` is the number of solution frequency maps. The `n + |C|^2` part is for storing the graph and input words.
**Pros:** Highly efficient and practical for the given constraints (`|C| <= 16`).; The complexity is polynomial in `n` and exponential only in `|C|`, which is small.; Correctly identifies all minimal, non-permutation-equivalent solutions by systematically resolving cyclic dependencies.
**Cons:** The logic is complex, involving graph theory (SCCs) and combinatorics.; The number of solutions can grow exponentially with the number of SCCs and the `diff` values, although it's manageable under the given constraints.
### Explanation
This approach is based on a key insight: a frequency map `F` can form a valid supersequence if and only if for every SCC `S` in the character dependency graph, the total count of characters from `S` is sufficient to break all internal cycles. The condition is `sum(F[c] for c in S) >= count_of_internal_edges_in_S + 1`.

We can construct all minimal frequency maps that satisfy this condition for all SCCs.

**Algorithm Steps:**
1.  **Graph and Counts:**
    *   Create a map `counts[u][v]` to store the number of times word `"uv"` appears.
    *   Build a graph `G` with unique characters as nodes. Add edge `u->v` if `counts[u][v] > 0`.
    *   Calculate `max_local_freq[c]`, the max occurrences of `c` in any word (e.g., 2 for `"cc"`).
2.  **SCCs:** Find all SCCs of `G`.
3.  **Iterative Solution Building:**
    *   Initialize a `Set<int[]>` called `solutions` containing a single frequency map `F` where `F[c] = max_local_freq[c]`.
    *   For each SCC `S`:
        *   Calculate `internal_edges = sum(counts[u][v] for u,v in S)`.
        *   If `internal_edges == 0`, the SCC is trivial (a single node, no self-loop), so no cycles to break. Continue.
        *   `needed = internal_edges + 1`.
        *   Create a `next_solutions` set. For each `f` in `solutions`:
            *   `current_chars = sum(f[c] for c in S)`.
            *   `diff = needed - current_chars`.
            *   If `diff > 0`, we must add `diff` characters from `S`. We find all combinations with repetition of picking `diff` characters from `S`. For each combination, we create a new frequency map by adding the chosen characters to `f` and add it to `next_solutions`.
            *   If `diff <= 0`, `f` is already valid for this SCC, so add `f` to `next_solutions`.
        *   Replace `solutions` with `next_solutions`.
4.  **Final Result:** The `solutions` set now contains all minimal frequency maps. Convert it to the required output format, ensuring no permutations are included by using a canonical representation (e.g., sorted tuple of counts) for uniqueness checks.

```java
// Simplified conceptual code for the SCC-based approach
class SCCApproach {
    public List<int[]> getFrequencies(String[] words) {
        // 1. Build graph, count edges, find unique characters
        Map<Character, Map<Character, Integer>> adj = new HashMap<>();
        // ... build graph and counts ...

        // 2. Find SCCs using Tarjan's or Kosaraju's algorithm
        List<Set<Character>> sccs = findSCCs(adj);

        // 3. Calculate base frequency map from max local frequencies
        int[] baseFreq = new int[26];
        // ... for (word : words) ...

        // 4. Iteratively build solutions
        Set<List<Integer>> solutions = new HashSet<>();
        solutions.add(toList(baseFreq));

        for (Set<Character> scc : sccs) {
            if (scc.size() == 1 && !adj.get(scc.iterator().next()).containsKey(scc.iterator().next())) {
                continue; // Trivial SCC
            }

            int internalEdges = 0;
            for (char u : scc) {
                for (char v : scc) {
                    internalEdges += adj.getOrDefault(u, Collections.emptyMap()).getOrDefault(v, 0);
                }
            }

            if (internalEdges == 0) continue;

            int needed = internalEdges + 1;
            Set<List<Integer>> nextSolutions = new HashSet<>();

            for (List<Integer> freqList : solutions) {
                int[] f = toArray(freqList);
                int currentChars = 0;
                for (char c : scc) {
                    currentChars += f[c - 'a'];
                }

                int diff = needed - currentChars;
                if (diff <= 0) {
                    nextSolutions.add(freqList);
                } else {
                    // Find all combinations of adding 'diff' chars from 'scc'
                    List<char[]> combinations = findCombinations(new ArrayList<>(scc), diff);
                    for (char[] combo : combinations) {
                        int[] newFreq = f.clone();
                        for (char c : combo) {
                            newFreq[c - 'a']++;
                        }
                        nextSolutions.add(toList(newFreq));
                    }
                }
            }
            solutions = nextSolutions;
        }

        // 5. Final filtering and formatting
        // The use of Set<List<Integer>> already handles uniqueness.
        // We might need to filter for permutations if the problem requires it.
        // The problem asks for non-permutation SCSs, so we need to store a canonical form.
        Set<List<Integer>> finalUniqueSols = new HashSet<>();
        for(List<Integer> sol : solutions) {
            List<Integer> nonZeroFreqs = new ArrayList<>();
            for(int count : sol) if(count > 0) nonZeroFreqs.add(count);
            Collections.sort(nonZeroFreqs);
            finalUniqueSols.add(nonZeroFreqs);
        }
        // Convert finalUniqueSols back to 26-element arrays and return.
        return new ArrayList<>(); // Placeholder
    }

    // Helper methods: findSCCs, findCombinations, toList, toArray...
}
```
### Algorithm
1.  **Build Character Dependency Graph:** Construct a directed multigraph `G` where nodes are the unique characters `C` present in `words`. For each word `"uv"`, add a directed edge from `u` to `v`.
2.  **Find Strongly Connected Components (SCCs):** Use Tarjan's algorithm or Kosaraju's algorithm to find all SCCs of `G`.
3.  **Calculate Base Frequency Map:** For each character `c`, find the maximum number of times it appears in any single word (e.g., 2 for `"aa"`, 1 for `"ac"`). This gives a base frequency map, `F`, which is a lower bound on the counts.
4.  **Process Each SCC:** The dependencies between SCCs form a DAG. We can satisfy dependencies within each SCC independently. For each SCC `S`:
    a.  Calculate `internal_edges`, the number of edges `u -> v` where both `u` and `v` are in `S`.
    b.  If `internal_edges > 0`, the SCC contains cycles. To break these cycles, the total number of character instances from `S` in the supersequence must be at least `internal_edges + 1`.
    c.  Let `current_chars_in_S` be the sum of frequencies in the current map `F` for characters in `S`.
    d.  If `current_chars_in_S < internal_edges + 1`, we need to add `diff = (internal_edges + 1) - current_chars_in_S` more characters, chosen from `S`.
5.  **Generate All Minimal Frequency Maps:** The core idea is that different ways of adding these `diff` characters can lead to different minimal SCSs that are not permutations. We maintain a set of solution frequency maps.
    a.  Start with a set containing just the base frequency map `F`.
    b.  For each SCC that needs `diff > 0` additional characters, expand the set of solutions. For each existing solution map, generate new maps by adding `diff` characters from the SCC in all possible ways (a combinatorial problem).
6.  **Filter Permutations:** After processing all SCCs, the resulting set of frequency maps may contain permutations of each other. Filter this set to keep only unique frequency maps. This can be done by sorting the 26-element frequency array and storing it in a set.