Count reverse-complement DNA strand pairs

Two strands form a special pair when one is the reverse complement of the
other: reverse the strand, then swap A↔T and C↔G. Reverse complement is an
involution (rc(rc(s)) == s), so the relation is symmetric. Checking
strands[j] == rc(strands[i]) covers both directions.

Brute force. Compare every pair (i, j), computing rc(strands[i]) and
comparing strings. That is O(n² · L) for n strands of length up to L. It is
fine to state, but it times out at n = 10^5.

Hash map, one pass. Walk the strands left to right. Keep a map of
strand -> how many times it appeared so far. For each strand s, every
earlier copy of rc(s) forms a pair with it, so add seen[rc(s)] to the
answer, then record s. Each pair (i, j) is counted exactly once, at the
moment j is processed.

Invariant: after processing index j, total equals the number of special
pairs with both indices ≤ j, and seen holds the counts of strands 0..j.

Edge cases that trip people up:

• Self-complementary strands (palindromes in the DNA sense, e.g. ACGT,
  AT). Here rc(s) == s, so k copies give k·(k−1)/2 pairs. The
  "look left, then insert" order handles this. Inserting first would pair a
  strand with itself.
• Odd-length strands can never be self-complementary, because the middle
  base would have to be its own complement.
• Reverse vs. reverse complement. AC and CA are reverses but not a
  pair. AC pairs with GT.
• Reject characters outside ACGT instead of silently mismatching.

To list the pairs rather than count them, store the indices for each strand
instead of a count. The work is then O(total length + number of pairs). That
is the best possible, since the output itself can be Θ(n²), e.g. n/2 copies of
A and n/2 copies of T.

from collections import defaultdict

_COMPLEMENT = str.maketrans("ACGT", "TGCA")
_VALID = frozenset("ACGT")


def reverse_complement(strand: str) -> str:
    """Reverse the strand and swap A<->T, C<->G."""
    return strand.translate(_COMPLEMENT)[::-1]


def _check(strand: str) -> None:
    if not strand or not set(strand) <= _VALID:
        raise ValueError(f"invalid strand: {strand!r}")


def count_special_pairs(strands: list[str]) -> int:
    """Number of index pairs i < j where strands[j] == reverse_complement(strands[i])."""
    seen: dict[str, int] = defaultdict(int)  # strand -> occurrences so far
    total = 0
    for s in strands:
        _check(s)
        total += seen[reverse_complement(s)]  # partners to the left of s
        seen[s] += 1
    return total


def list_special_pairs(strands: list[str]) -> list[tuple[int, int]]:
    """All special pairs (i, j), i < j, sorted. Output-sensitive: O(total length + pairs)."""
    positions: dict[str, list[int]] = defaultdict(list)
    pairs: list[tuple[int, int]] = []
    for j, s in enumerate(strands):
        _check(s)
        for i in positions.get(reverse_complement(s), []):
            pairs.append((i, j))
        positions[s].append(j)
    pairs.sort()
    return pairs


class SpecialPairCounter:
    """Streaming version: strands arrive one at a time, query the running count."""

    def __init__(self) -> None:
        self._seen: dict[str, int] = defaultdict(int)
        self._total = 0

    def add(self, strand: str) -> int:
        """Add a strand; return how many new special pairs it created."""
        _check(strand)
        new_pairs = self._seen[reverse_complement(strand)]
        self._seen[strand] += 1
        self._total += new_pairs
        return new_pairs

    def remove(self, strand: str) -> int:
        """Remove one copy of a strand; return how many pairs disappeared."""
        if self._seen.get(strand, 0) == 0:
            raise KeyError(strand)
        self._seen[strand] -= 1
        lost = self._seen[reverse_complement(strand)]
        self._total -= lost
        return lost

    @property
    def total(self) -> int:
        return self._total

Let n be the number of strands and S the total number of characters.

• reverse_complement: O(L) time and space for a strand of length L.
• count_special_pairs: O(S) expected time, since each strand is hashed and
  reverse-complemented once. Space O(S) for the map keys.
• list_special_pairs: O(S + P log P) time where P is the number of pairs
  (the sort; drop it and output is already grouped by j). Space O(S + P).
• SpecialPairCounter.add / remove: O(L) each. total is O(1). Space
  O(S) over all live strands.

• ["AACG", "CGTT", "GGA", "TCC", "CGTT"] → count 3, pairs
  [(0, 1), (0, 4), (2, 3)].
• ["ACGT", "ACGT", "ACGT"] → 3 (self-complementary, C(3,2)).
• ["AT", "AT"] → [(0, 1)].
• ["A", "T", "A", "T"] → 4 (each A with each T).
• ["AC", "CA"] → 0 (reverse only, not reverse complement).
• ["A"] → 0. [] → 0.
• ["ACGU"] → ValueError (invalid base).
• Randomized: 300 random lists of short strands, checked against the O(n²)
  brute force for both the count and the pair list.

1. Streaming / deletions. Strands arrive and leave over time; report the
   running count. Keep the same counter map. On add(s) add seen[rc(s)]
   before incrementing. On remove(s) decrement first, then subtract
   seen[rc(s)]. That order is what keeps self-complementary strands correct.
   See SpecialPairCounter.
2. Very long strands / memory. Store a hash of each strand instead of the
   string. Use a rolling (polynomial) hash and compute the hash of rc(s) in
   the same pass, by reading s backwards with complemented bases. That avoids
   building the reversed string. Mention collisions: use 64-bit or double
   hashing, and verify on a hit when exactness matters.
3. Allow one mismatch. A pair is special if strands[j] differs from
   rc(strands[i]) in at most one position (equal lengths). For each strand,
   generate L wildcard keys (rc(s) with position p replaced by *) and
   look up how many earlier strands produced the same masked key. Exact matches
   appear under all L keys, so count them separately and subtract (L−1)·exact.
   Cost O(S · L) for the masked strings, or O(S) with hashes.
4. Partial overlap. Two strands pair if a suffix of one, of length ≥ k,
   is the reverse complement of a prefix of the other (how strands anneal).
   Index the length-k reverse-complemented prefixes in a hash map, or use a
   trie/Aho-Corasick over reverse complements. Then for each strand check its
   suffixes. Discuss O(S · L) vs. automaton approaches.
5. Distributed data set. Billions of strands across machines. Shard by
   the canonical key min(s, rc(s)), so a strand and its partners land on the
   same shard. Each shard computes C(k,2) for self-complementary keys or
   count[s] · count[rc(s)] otherwise, then sum across shards.

Mid-level (L4)

• Defines reverse complement correctly and states the O(n²) brute force.
• Reaches the one-pass hash map and gets the count right on a simple example.
• Handles empty input and invalid bases when prompted.

Senior (L5)

• Spots the self-complementary case without a hint and explains why "look up,
  then insert" avoids self-pairing.
• Gives precise complexity in terms of total characters, not just n.
• Distinguishes counting from listing, and notes the output can be Θ(n²).
• Extends cleanly to streaming adds and removes.

Staff (L6+)

• Proposes the canonical form min(s, rc(s)) and uses it for sharding and
  for the closed-form count.
• Talks through rolling hashes for long strands, collision risk, and when to
  verify.
• Handles the one-mismatch and overlap variants with sound complexity
  arguments and clear trade-offs.