We get to cheat a little bit more, actually.
If $q = aXbYbZa$ is a pattern, then $bYb$ occurs at least as many times as $q$. Thus, we only need to find patterns $cWc$ where $W$ contains no repeats and does not contain $c$. This means that the length of $q$ is at most $k+1$
We are going to build a trie-like structure where each node contains the number of times the string representing that node has been seen.
for i: each index of s
simultaneously insert s[i:i],s[i:i+1],...,s[i:i+k] into the trie by
inserting s[i:i+k] but incrementing the count on each node while descending the trie
traverse the trie
keep track of the node with the highest count which represents a string of the form aXa
reproduce the string with the highest count from the trie and return it
The running time for this is $O(kn)$. While building the trie, we touch $k$ nodes for each index of $s$. The trie has only $O(kn)$ nodes, so traversing it takes only $O(kn)$ time.