Frequencies of Shortest Supersequences

Frequencies of Shortest Supersequences

What is this problem about?

The Frequencies of Shortest Supersequences interview question is an advanced string and graph problem. You are given a set of short strings (or rules) and you need to find the shortest possible "supersequence" that contains all of them as subsequences. Since there can be multiple shortest supersequences, the problem specifically asks for the character frequencies of all valid shortest supersequences.

Why is this asked in interviews?

This is a highly complex Graph and Combinatorics coding problem asked by top-tier companies. It is an extension of the classic "Shortest Common Supersequence" problem. It evaluates a candidate's ability to combine Topological Sorting (to satisfy ordering constraints) with Bitmask DP or exhaustive search to handle conflicting orderings and find all minimal-length valid combinations.

Algorithmic pattern used

This problem usually requires transforming the constraints into a Directed Graph and finding the optimal Topological Sort.

1. Build a graph where an edge u -> v means character u must appear before v.
2. Identify cycles. Cycles indicate that you cannot satisfy the ordering without duplicating characters.
3. If you must break a cycle, you have to add an extra instance of a character. The goal is to break all cycles with the minimum number of character additions.
4. This often translates to finding the Minimum Feedback Arc Set, which is NP-hard, but constraints are usually small enough for Bitmask DP.

Example explanation

Suppose rules are "ab" and "ba".

1. "ab" means 'a' before 'b'. "ba" means 'b' before 'a'.
2. Graph: a -> b and b -> a. This is a cycle.
3. To satisfy both as subsequences, you can't just have "ab". You need "aba" (contains "ab" and "ba") or "bab" (contains "ba" and "ab").
4. Both have length 3.
5. Frequencies for "aba": a: 2, b: 1. Frequencies for "bab": a: 1, b: 2. You would return both frequency sets.

Common mistakes candidates make

• Standard SCS DP: Trying to use the standard 2D DP for Longest Common Subsequence, which only works well for two strings, not a set of multiple short rules.
• Ignoring Cycles: Failing to realize that cyclic dependencies strictly dictate the need for character duplication.
• Complexity: Trying to generate all possible strings, which is computationally impossible. You must work on the graph of constraints, not the strings themselves.

Interview preparation tip

When dealing with multiple subsequence constraints, always think of Directed Graphs. A path in the graph represents a valid sequence. A cycle represents a contradiction that forces you to increase the length of your supersequence by duplicating nodes.