Count reverse-complement DNA strand pairs

You are given a list of DNA strands. Each strand is a non-empty string over the alphabet A, C, G, T.

The reverse complement of a strand is formed by reversing it and then replacing each base with its partner: A with T, T with A, C with G, and G with C. For example, the reverse complement of AACG is CGTT.

Two strands at indices i < j form a special pair when strands[j] is the reverse complement of strands[i]. Because taking the reverse complement twice gives back the original strand, the relation is symmetric.

Implement:

• count_special_pairs(strands: list[str]) -> int: the number of special pairs.
• list_special_pairs(strands: list[str]) -> list[tuple[int, int]]: every special pair (i, j) with i < j, sorted.

Raise ValueError if a strand is empty or contains a character outside ACGT.

Constraints

• 0 <= len(strands) <= 10^5
• The total length of all strands is at most 10^6.
• Strands may repeat. Every copy counts as a separate index.

Example 1

strands = ["AACG", "CGTT", "GGA", "TCC", "CGTT"]
count_special_pairs(strands)  -> 3
list_special_pairs(strands)   -> [(0, 1), (0, 4), (2, 3)]

CGTT is the reverse complement of AACG (twice), and TCC is the reverse complement of GGA.

Example 2

strands = ["ACGT", "ACGT", "AC", "CA"]
count_special_pairs(strands)  -> 1

ACGT is its own reverse complement, so its two copies form one pair. AC and CA are only reverses of each other, so they do not form a pair (the reverse complement of AC is GT).

Reconstructed from the reported question; details may differ from what interviewers ask.