Assemble DNA payload strings from tagged fragments

You are given a list of DNA-like fragments. Each fragment is a tuple:

• start_tag: string
• end_tag: string
• payload: string

A valid DNA chain is formed by ordering fragments so that the end_tag of one fragment matches the start_tag of the next fragment. The assembled DNA string is the concatenation of payloads in chain order.

Assume tags are arbitrary strings (e.g., "AAA", "AAC").

Q1: Single forward chain

Given fragments that form exactly one continuous chain using the rule prev.end_tag == next.start_tag, assemble and output the final concatenated string.

Example:

Input:

• (XXX, ATG, "Hello")
• (ATG, GCA, "World")
• (GCA, TAG, "!")
• (TAG, YYY, "Done")

Output:

• "HelloWorld!Done"

Q2: Chain can be traversed in either direction

Now treat each fragment as connecting two tags, and you may traverse the final chain either in the forward direction or in the reverse direction.

• Forward traversal outputs payloads in forward order.
• Reverse traversal outputs payloads in reverse order.
• Either output is acceptable.

For the example above, valid outputs include:

• "HelloWorld!Done" (forward)
• "Done!WorldHello" (reverse)

Q3: Multiple DNA chains

Now the input fragments may form multiple disjoint chains (still assuming they can be arranged into simple chains with no branching within a chain). Output all assembled strings, one per chain, in any order.

Output format

• Q1/Q2: a single string
• Q3: a list/array of strings (one per chain)

Part 1: Assemble a Single Forward DNA Chain

You are given a list of DNA-like fragments. Each fragment is a tuple (start_tag, end_tag, payload). The fragments are guaranteed to form exactly one directed continuous chain, meaning the end_tag of each fragment matches the start_tag of the next fragment. Assemble the chain and return the concatenation of the payload strings in chain order. If the input list is empty, return the empty string.

Constraints

• 0 <= len(fragments) <= 100000
• Each start_tag, end_tag, and payload is a string.
• For non-empty input, the fragments form one valid directed path with no branching.
• No tag has more than one outgoing fragment or more than one incoming fragment.
• The total length of all payload strings is at most 1000000.

Examples

Example 1

Input: ([('XXX', 'ATG', 'Hello'), ('ATG', 'GCA', 'World'), ('GCA', 'TAG', '!'), ('TAG', 'YYY', 'Done')],)
Output: 'HelloWorld!Done'

Explanation: The fragments are already in chain order.

Example 2

Input: ([('B', 'C', '2'), ('A', 'B', '1'), ('C', 'D', '3')],)
Output: '123'

Explanation: The correct chain is A -> B -> C -> D, so the payload order is 1, 2, 3.

Hints

1. Think of each fragment as a directed edge from start_tag to end_tag.
2. The first fragment starts at the tag that appears as a start_tag but never as an end_tag.

Part 2: Assemble a DNA Chain Traversable in Either Direction

You are given a list of DNA-like fragments. Each fragment is a tuple (tag_a, tag_b, payload). This time, treat each fragment as an undirected connection between two tags. The fragments are guaranteed to form one simple chain with no branching. You may traverse the chain from either endpoint. When traversing, output each fragment's payload in traversal order; the payload string itself is not reversed. Conceptually, either direction is a valid assembly. For deterministic results in this problem, return the assembly obtained by starting from the lexicographically smallest endpoint tag. If the input list is empty, return the empty string.

Constraints

• 0 <= len(fragments) <= 100000
• Each tag_a, tag_b, and payload is a string.
• For non-empty input, the fragments form one simple undirected path with no branching.
• Each tag has undirected degree at most 2.
• The total length of all payload strings is at most 1000000.

Examples

Example 1

Input: ([('XXX', 'ATG', 'Hello'), ('ATG', 'GCA', 'World'), ('GCA', 'TAG', '!'), ('TAG', 'YYY', 'Done')],)
Output: 'HelloWorld!Done'

Explanation: The endpoints are XXX and YYY. Starting from XXX gives the forward payload order.

Example 2

Input: ([('M', 'Z', 'middle'), ('A', 'M', 'start')],)
Output: 'startmiddle'

Explanation: The endpoints are A and Z. Starting from A visits payloads start, then middle.

Hints

1. Build an undirected adjacency list where each edge stores its payload.
2. A chain endpoint is a tag with degree 1. Start from the smaller endpoint and walk without going back over the edge you just used.

Part 3: Assemble Multiple Forward DNA Chains

You are given a list of DNA-like fragments. Each fragment is a tuple (start_tag, end_tag, payload). The fragments may belong to multiple disjoint directed chains. Within each chain, fragments are ordered by the rule that the end_tag of one fragment equals the start_tag of the next fragment. There is no branching within any chain. Return the assembled payload string for every chain. Conceptually, the chains may be returned in any order; for deterministic results in this problem, return the assembled strings sorted lexicographically.

Constraints

• 0 <= len(fragments) <= 100000
• Each start_tag, end_tag, and payload is a string.
• The fragments form zero or more disjoint directed paths.
• No tag has more than one outgoing fragment or more than one incoming fragment.
• The total length of all payload strings is at most 1000000.

Examples

Example 1

Input: ([('A', 'B', 'Hi'), ('C', 'D', 'Bye')],)
Output: ['Bye', 'Hi']

Explanation: There are two one-fragment chains. The returned list is sorted lexicographically.

Example 2

Input: ([('M', 'N', 'b'), ('A', 'B', 'x'), ('B', 'C', 'y'), ('N', 'O', 'c')],)
Output: ['bc', 'xy']

Explanation: The chains are M -> N -> O producing bc, and A -> B -> C producing xy.

Hints

1. Use indegree and outdegree to find the starting tag of each chain.
2. After finding every start tag, traverse each chain exactly once and collect its payloads.