Frequencies of Shortest Supersequences

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.

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.

1// This is a conceptual illustration. A direct implementation is not feasible due to complexity.2class BruteForceApproach {3    // n = words.length4    // Map<Integer, Integer> memo = new HashMap<>(); // memo[pmask] -> minLength5    // Map<Integer, Set<int[]>> solutions = new HashMap<>(); // memo[pmask] -> set of frequency maps6 7    public void findSCS(int pmask, int[] currentFreqs, String[] words) {8        // Base case: all words satisfied9        if (pmask == (1 << words.length) - 1) {10            // Process the found supersequence's frequency map11            return;12        }13 14        // Pruning using memoization15        int currentLength = 0;16        for (int f : currentFreqs) currentLength += f;17        // if (memo.containsKey(pmask) && currentLength >= memo.get(pmask)) {18        //     return;19        // }20 21        // Find all possible next characters22        Set<Character> nextChars = new HashSet<>();23        for (int i = 0; i < words.length; i++) {24            int ptr = (pmask >> i) & 1;25            nextChars.add(words[i].charAt(ptr));26        }27 28        // Explore transitions29        for (char c : nextChars) {30            int nextPmask = pmask;31            for (int i = 0; i < words.length; i++) {32                int ptr = (pmask >> i) & 1;33                if (words[i].charAt(ptr) == c) {34                    nextPmask |= (1 << i);35                }36            }37            38            // Recursive call39            currentFreqs[c - 'a']++;40            findSCS(nextPmask, currentFreqs, words);41            // Backtrack42            currentFreqs[c - 'a']--;43        }44    }45}

This approach is primarily educational to understand the problem's complexity. The state space of 2^n makes it impractical for the given constraints.

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.

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.

1// Simplified conceptual code for the SCC-based approach2class SCCApproach {3    public List<int[]> getFrequencies(String[] words) {4        // 1. Build graph, count edges, find unique characters5        Map<Character, Map<Character, Integer>> adj = new HashMap<>();6        // ... build graph and counts ...7 8        // 2. Find SCCs using Tarjan's or Kosaraju's algorithm9        List<Set<Character>> sccs = findSCCs(adj);10 11        // 3. Calculate base frequency map from max local frequencies12        int[] baseFreq = new int[26];13        // ... for (word : words) ...14 15        // 4. Iteratively build solutions16        Set<List<Integer>> solutions = new HashSet<>();17        solutions.add(toList(baseFreq));18 19        for (Set<Character> scc : sccs) {20            if (scc.size() == 1 && !adj.get(scc.iterator().next()).containsKey(scc.iterator().next())) {21                continue; // Trivial SCC22            }23 24            int internalEdges = 0;25            for (char u : scc) {26                for (char v : scc) {27                    internalEdges += adj.getOrDefault(u, Collections.emptyMap()).getOrDefault(v, 0);28                }29            }30 31            if (internalEdges == 0) continue;32 33            int needed = internalEdges + 1;34            Set<List<Integer>> nextSolutions = new HashSet<>();35 36            for (List<Integer> freqList : solutions) {37                int[] f = toArray(freqList);38                int currentChars = 0;39                for (char c : scc) {40                    currentChars += f[c - 'a'];41                }42 43                int diff = needed - currentChars;44                if (diff <= 0) {45                    nextSolutions.add(freqList);46                } else {47                    // Find all combinations of adding 'diff' chars from 'scc'48                    List<char[]> combinations = findCombinations(new ArrayList<>(scc), diff);49                    for (char[] combo : combinations) {50                        int[] newFreq = f.clone();51                        for (char c : combo) {52                            newFreq[c - 'a']++;53                        }54                        nextSolutions.add(toList(newFreq));55                    }56                }57            }58            solutions = nextSolutions;59        }60 61        // 5. Final filtering and formatting62        // The use of Set<List<Integer>> already handles uniqueness.63        // We might need to filter for permutations if the problem requires it.64        // The problem asks for non-permutation SCSs, so we need to store a canonical form.65        Set<List<Integer>> finalUniqueSols = new HashSet<>();66        for(List<Integer> sol : solutions) {67            List<Integer> nonZeroFreqs = new ArrayList<>();68            for(int count : sol) if(count > 0) nonZeroFreqs.add(count);69            Collections.sort(nonZeroFreqs);70            finalUniqueSols.add(nonZeroFreqs);71        }72        // Convert finalUniqueSols back to 26-element arrays and return.73        return new ArrayList<>(); // Placeholder74    }75 76    // Helper methods: findSCCs, findCombinations, toList, toArray...77}