Strings

BA1A — Compute the Number of Times a Pattern Appears in a Text

solved Problem statement

BA1B — Find the Most Frequent Words in a String

solved Problem statement

Shows a real distinction: kmer_count() tallies canonical k-mers, pooling each with its reverse complement, so it reports GCAT and ATGC as one count of 4. This problem wants literal occurrences, so it counts the raw windows from kmers().

BA1D — Find All Occurrences of a Pattern in a String

solved Problem statement

BA9G — Construct the Suffix Array of a String

solved Problem statement

Suffix arrays were one of three gaps this pack was built to measure. They are a builtin now, which is what LREP and MREP in the Stronghold pack stand on.

BA1E — Find Patterns Forming Clumps in a String

solved Problem statement

A sliding window with a tally inside it. A k-mer qualifies once, so the answers are a set.

BA1H — Find All Approximate Occurrences of a Pattern

solved Problem statement

hamming_distance is a builtin, so this is a windowed scan and nothing more.

BA1I — Most Frequent Words with Mismatches

solved Problem statement

The answer need not occur in the text at all. Tallying each window's neighbourhood is the same arithmetic over far fewer strings than testing all 4^k candidates.

BA1J — Frequent Words with Mismatches and Reverse Complements

solved Problem statement

A site can sit on either strand, so a k-mer is credited for its reverse complement too — which is why the winners differ from BA1I on the same input.

BA1N — Generate the d-Neighborhood of a String

solved Problem statement

Grown one position at a time, dropping any prefix that has already spent more than d substitutions.

BA2A — Implement MotifEnumeration

solved Problem statement

A motif need not occur exactly anywhere, so the candidates are the neighbourhoods of the first string's windows: anything qualifying must be within d of one of them.

BA2B — Find a Median String

solved Problem statement

Every k-mer is a candidate, not only those occurring in the strings. Any minimiser is accepted, so the assertion checks the distance rather than the string: this finds ACG where the sample shows GAC, and both score 2.

BA2H — Implement DistanceBetweenPatternAndStrings

solved Problem statement

Best per string, summed across them: a motif only has to occur once in each.

BA9D — Find the Longest Repeat in a String

solved Problem statement

The largest entry in the LCP array, and nothing else. Two suffixes sharing a long prefix is what a repeat is, so the array has already found every one of them before the problem is read.

BA9E — Find the Longest Substring Shared by Two Strings

solved Problem statement

Concatenate with a separator, then take the largest LCP between neighbouring suffixes that came from different sides. The separator is load-bearing: without it a match can run across the join and name a substring neither string contains.

BA9I — Construct the Burrows-Wheeler Transform of a String

solved Problem statement

Sorting rotations and sorting suffixes agree once the string ends in a sentinel, so the suffix array gives the transform directly — the character before each sorted suffix.

BA9J — Reconstruct a String from its Burrows-Wheeler Transform

solved Problem statement

The k-th occurrence of a symbol in the first column is the k-th in the last. That correspondence alone rebuilds the text, which is why the transform can be stored without anything beside it.

BA9A — Construct a Trie from a Collection of Patterns

solved Problem statement

Patterns sharing a prefix share a path, so the trie is walked once per text position no matter how many patterns there are. Node numbering is explicitly free, so the assertions are structural: every pattern spellable, no node with two edges on one symbol.

BA9B — Implement TrieMatching

solved Problem statement

Every pattern is tested at once by a single walk, so the cost is the text length times the longest pattern rather than times the pattern count. Cross-checked against a plain scan.

BA9H — Pattern Matching with the Suffix Array

solved Problem statement

The same answer as BA9B reached the other way, and the example says which to reach for: a trie is built from the patterns and suits many patterns against one text; a suffix array is built from the text and suits one text queried repeatedly.

BA9K — Generate the Last-to-First Mapping of a String

solved Problem statement

The kth occurrence of a symbol in one column is the kth in the other, so a row is found by counting rather than searching. Asserted to be a bijection over every row, which is what makes the walk in BA9J terminate.

BA9L — Implement BWMatching

solved Problem statement

Searching the transform without ever rebuilding the text: sorted rows mean every match forms one contiguous band, narrowed one symbol at a time. Cross-checked by inverting the transform — the point being that the search never needed to.

BA9M — Implement BetterBWMatching

solved Problem statement

Two precomputed tables remove BWMatching's scan, so a query costs time proportional to the pattern rather than to the text. That difference is what makes indexing a genome once and querying it billions of times practical.

BA9Q — Construct the Partial Suffix Array of a String

solved Problem statement

A full suffix array of a human genome is 12 GB before the sequence itself. Keeping every Kth value cuts that by a factor of K, with the rest recoverable by walking the BWT — the compromise real read aligners ship with.

BA9C — Construct the Suffix Tree of a String

solved Problem statement

A trie of every suffix with non-branching chains collapsed. That collapse is what makes it linear rather than quadratic — a trie of all suffixes has O(n^2) nodes and almost all have one child. Built directly here; Ukkonen's algorithm is linear but obscures the structure at this size.

BA9F — Find the Shortest Non-Shared Substring of Two Strings

solved Problem statement

Shortest first, which makes the answer minimal by construction: if a substring of length k is absent, everything containing it is absent too. Returns CC where the sample shows AA; the assertion proves no one-character answer exists.

BA9N — Find All Occurrences of a Collection of Patterns in a String

solved Problem statement

BA9L and BA9M count occurrences without locating them, because a BWT band gives rows of the sorted matrix rather than text positions. Turning a row back into a position is what the suffix array supplies — the partial one of BA9Q in a real aligner, since the full one would undo the memory saving.

BA9O — Find All Approximate Occurrences of a Collection of Patterns in a String

solved Problem statement

Reads carry errors and genomes carry variants, so exact matching finds nothing useful and every aligner is an approximate matcher. Position 4 appears twice because two patterns match there — the answer lists occurrences, not distinct positions.

BA9P — Implement TreeColoring

solved Problem statement

How BA9E's shared-substring question is answered on a generalised suffix tree: colour leaves by which string they came from, and an internal node goes purple exactly when its substring occurs in both.

BA9R — Construct a Suffix Tree from a Suffix Array

solved Problem statement

BA9C built the tree by collapsing a suffix trie, which is quadratic before the collapse. The suffix and LCP arrays carry the same information in two flat integer arrays and rebuild the tree in one pass — which is why real tools store the arrays and never materialise the tree.