Frequencies of Shortest Supersequences - Solution & Explanation

Problem Overview: You are given ordering constraints between characters (for example "ab" meaning a must appear before b). The task is to construct the shortest possible supersequence that satisfies every constraint and return the possible frequency distributions of characters among all shortest valid supersequences.

The difficulty comes from cycles in the ordering graph. If a → b and b → a both exist, a single occurrence of each character cannot satisfy both constraints. The only way to resolve the cycle is to duplicate at least one character so it can appear both before and after another character.

Approach 1: Graph Modeling + Bitmask Enumeration + Topological Sort (O(2^k * (V + E)) time, O(V + E) space)

First model the constraints as a directed graph where each character is a node and every pair "ab" creates an edge a → b. Let k be the number of distinct characters involved. Each character must appear at least once, but some characters may need to appear twice to break cycles. Use bitmask enumeration over the k characters to represent which characters are duplicated.

For every mask, assume characters in the mask appear twice while others appear once. Then check whether the constraints can be satisfied without contradiction. This check is done using topological sort on the directed graph. If the ordering constraints among the single-occurrence characters create a cycle that cannot be resolved by the duplicated ones, discard the mask. Otherwise the mask represents a valid supersequence configuration.

Track the total length of the sequence for each mask: length = k + popcount(mask). Maintain the minimum possible length. For masks producing the minimum length, record the resulting frequency vector where each character has frequency 1 or 2 depending on the mask.

The enumeration works because the alphabet size is small. Bitmasking efficiently explores all duplication combinations while the graph validation step ensures constraints are satisfied. This combines techniques from graph algorithms, topological sorting, and bit manipulation.

Recommended for interviews: The bitmask + topological sort strategy is the expected solution. A naive attempt to generate actual supersequences explodes combinatorially. Recognizing that only which characters are duplicated matters reduces the search space dramatically. Enumerating duplication masks shows strong problem decomposition skills, while validating them with topological sorting demonstrates solid graph fundamentals.