(Challenge) Bacteria Synthesis

Chef Ada always prepares delicious and nutritious dishes. Her secret is to use genetic engineering of bacteria to synthesise proteins. A protein is denoted by a string of uppercase English characters 'A'-'T'; each character represents an amino acid. The genome of Ada's bacteria is also denoted by a string with length $N$. Each character of this string is 'A', 'C', 'T' or 'G', representing a nucle