Subtask 1 ($N \le 100$):

Given a string, we can count the frequency of every kind of moo. Let $count[abb]$ represent the number of occurrences of the moo $abb$. We can iterate over every substring of length $3$ and if it is a valid moo, increment its number of occurrences. If any value of $count[abb] \geq F$ at any time, we know that $abb$ is a valid moo. This count function takes $O(N)$.

Since any character of our string could have been corrupted, we can iterate over all $N$ characters and try all $A$ possible replacements where $A$ is the size of the alphabet ($26$ for all lowercase letters). This gives a total time complexity of $O(AN^2)$.

My Python Code:

from collections import defaultdict
N,F = map(int,input().split())
S = input()
possible_moos = set()

def find_moos(s):
    count = defaultdict(int)
    for i in range(0,N-2):
        if s[i] != s[i+1] and s[i+1] == s[i+2]:
            count[s[i:i+3]] += 1
            if (count[s[i:i+3]] >= F):
                possible_moos.add(s[i:i+3])

for i in range(0,N):
    for j in range(26):
        scopy = S[:i]+chr(j+ord('a'))+S[i+1:]
        find_moos(scopy)
possible_moos = sorted(possible_moos)
print(len(possible_moos))
for moo in possible_moos:
    print(moo)

Full Credit:

In the previous subtask, we end up counting a lot of the same substrings and duplicating our work. Instead, we can make the observation that changing a single character only affects the counts for $3$ substrings.

Since a moo must be length $3$, if we change one of the characters in our string to $x$, we make our new string $...##x## ...$ where $#$ represents some characters before and after our edited position. The only substrings that get changed as a result of this edit are $[##x, #x#, x##]$.

This leads us to the final solution sketch, where we count the frequency of moos in the original string. Then we can try all $A \times N$ edits (where we change a character in the string to each of the $A$ letters in our alphabet), but for each edit, updating the counts only takes $O(1)$ since we only need to update the counts for the $3$ substrings that got modified by our edit. More specifically, we decrement the count of the original substring and increment the count of the new substring by 1. This now runs in $O(AN)$.

Benjamin Qi's Python Code:

from collections import defaultdict
from string import ascii_lowercase
 
N, F = map(int, input().split())
S = input()
oc = defaultdict(int)
 
def is_moo(s):
	assert len(s) == 3
	return s[0] != s[1] == s[2]
 
for i in range(len(S)-2):
	s = S[i:i+3]
	if is_moo(s):
		oc[s] += 1
 
ans = set()
 
def add(pos, c, dif):
	for i in range(max(pos-2, 0), min(pos+1, len(S)-2)):
		s = list(S[i:i+3])
		s[pos-i] = c
		s_str = "".join(s)
		if is_moo(s_str):
			oc[s_str] += dif
			if oc[s_str] >= F:
				ans.add(s_str)
 
for i in range(len(S)):
	add(i, S[i], -1)
	for c in ascii_lowercase:
		add(i, c, 1)
		add(i, c, -1)
	add(i, S[i], 1)
 
ans = sorted(ans)
print(len(ans))
for m in ans:
	print(m)

Alex Liang's C++ code:

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n, f;
    string S;
    cin >> n >> f >> S;
 
    map<string, int> occ;
    set<string> ans;
 
    auto chk = [&](int i){
        if (i < 0 or i + 2 >= n)
            return false;
            
        return (S[i] != S[i + 1] and S[i + 1] == S[i + 2]);
    };
    auto updPoint = [&](int i, int delta){
        if (!chk(i))
            return;
        
        string t = S.substr(i, 3);
 
        occ[t] += delta;
 
        if (occ[t] >= f)
            ans.insert(t);
    };
    auto updRange = [&](int i, int delta){
        updPoint(i - 2, delta);
        updPoint(i - 1, delta);
        updPoint(i, delta);
    };
 
    for (int i = 0; i < n; i++)
        updPoint(i, 1);
    
    for (int i = 0; i < n; i++){
        char temp = S[i];
 
        for (char c = 'a'; c <= 'z'; c++){
            updRange(i, -1);
            S[i] = c;
            updRange(i, 1);
        }
        updRange(i, -1);
        S[i] = temp;
        updRange(i, 1);
    }
    
    cout << ans.size() << "\n";
 
    for (auto s : ans)
        cout << s << "\n";
}