String Reconstruction
Reconstruct a string based on its subsequences
Problem Statement
Imagine an unknown string composed of distinct characters. You are given several subsequences derived from it. Your goal is to reconstruct the original string if it can be uniquely determined; otherwise, return NULL.
For instance, suppose the unknown string is “adecf”, and you are provided the subsequences: “ae”, “dcf”, and “de”. If multiple valid strings satisfy all these subsequence constraints, you should return NULL; if only one such string exists, return that unique solution.
Assume that every character appears in at least one of the provided subsequences.
Examples:
Input: ["ae", "dcfe", "ad"]
Output: "adcfe"
Input: ["ab", "bc"]
Output: "abc"
Input: ["ae", "dcf", "de"]
Output: NULL
Explanation: Both "adcfe" and "daecf" are possible.
Input: ["ab", "ac"]
Output: NULL
Explanation: Both "abc" and "acb" are possible.Bonus Challenge: All Possible Reconstructions
What if the clues don’t guarantee a unique solution? In this variant, your task is to find all possible original strings that can be constructed using the given subsequences.
Creating a directed graph and doing a topological sort should do the trick? With added logic to catch multiple sequences and unconnected sub graphs
Also when we do khans we can use backtracking to get all valid sequences
from collections import defaultdict, deque
def reconstruct(subsequences):
chars = set("".join(subsequences))
g = defaultdict(set)
indeg = {c: 0 for c in chars}
for s in subsequences:
for a, b in zip(s, s[1:]):
if b not in g[a]:
g[a].add(b)
indeg[b] += 1
q = deque([c for c in chars if indeg[c] == 0])
res = []
while q:
if len(q) > 1:
return None
u = q.popleft()
res.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return "".join(res) if len(res) == len(chars) else None
print(reconstruct(["ae","dcfe","ad"]))
print(reconstruct(["ab","bc"]))
print(reconstruct(["ae","dcf","de"]))
print(reconstruct(["ab","ac"]))