Find the optimal pattern Given a string s composed of lowercase letters, such as

aabaaababbbbaaba


and a positive integer n, such as 4, output a length-n string t such that when t is repeated to the length of s, they have as many chars in common as possible. For the given example, the optimal output would be aaba, because it has thirteen chars in common with the target string:

s: aabaaababbbbaaba
t: aabaaabaaabaaaba (aaba)
   ^^^^^^^^  ^ ^^^^


and no possible t has more. However, for aaaaaab, there are two possible outputs: aaaa and aaba, which each have 6 chars in common with the target string:

s: aaaaaab
t: aaaaaaaa (aaaa)
   ^^^^^^ 

s: aaaaaab
t: aabaaaba (aaba)
   ^^ ^^^^


Either aaaa or aaba can be outputted, or both if you'd like. Note that s is not ever repeated; the trailing a in both repeated values of t is simply ignored.



Test cases

Inputs -&gt; Valid outputs
1 a -&gt; a
1 aa -&gt; a
2 aa -&gt; aa
1 ab -&gt; a b
2 ab -&gt; ab
1 abb -&gt; b
2 abb -&gt; ab bb
2 ababa -&gt; ab
2 abcba -&gt; ab
2 aabbbbb -&gt; bb  (ab is not a valid output here)
3 aababba -&gt; aab abb
3 aababbaa -&gt; aab
3 asdasfadf -&gt; asf
3 asdasfadfsdf -&gt; asf adf
2 abcdefghijklmnopqrstuvwxyzyx -&gt; yx
2 supercalifragilisticexpialidocious -&gt; ic ii
3 supercalifragilisticexpialidocious -&gt; iri ili ioi
4 supercalifragilisticexpialidocious -&gt; scii
5 supercalifragilisticexpialidocious -&gt; iapic
2 eeeebaadbaecaebbbbbebbbbeecacebdccaecadbbbaceebedbbbddadebeddedbcedeaadcabdeccceccaeaadbbaecbbcbcbea -&gt; bb be
10 bbbbacacbcedecdbbbdebdaedcecdabcebddbdcecebbeeaacdebdbebaebcecddadeeedbbdbbaeaaeebbedbeeaeedadeecbcd -&gt; ebbbdbeece ebdbdbeece
20 aabbbaaabaaabaaaabbbbabbbbabbbabbbbbabbaaaababbbaababbbaababaaaabbaaabbaabbbabaaabbabbaaabbaaaaaaaba -&gt; aabbbbaaabbabbbaabba


Rules


You may assume the input will only ever be a non-empty string of lowercase letters and a positive integer no greater than the length of the string.
You may take the inputs in any standard format and in either order.
You may output a single string, or more than one in the form of an array, separated by newlines or spaces, etc.
Your code must finish for each test-case in less than 1 minute on any fairly modern computer.
This is code-golf, so make your code as short as possible.
Jelly, 11 bytes

sZµṢŒrUṀṪµ€


Try it online!

Wasn't expecting to beat Dennis on this one, so tried to FGITW it (after trying several possibilities; there's more than one way to make 11). I came in shorter, much to my surprise.

Takes the string then the count as command-line arguments. Outputs on stdout.

Explanation

sZµṢŒrUṀṪµ€
s            Split {the first input} into {the second input}-sized groups
 Z           Transpose
  µ      µ€  On each of the transposed groups:
   Ṣ           Sort it;
    Œr         Run-length encode it;
      U        Rearrange it to the form {count, letter};
       Ṁ       Take the largest element (i.e. largest count)
        Ṫ      Take the second element of the pair (i.e. just the letter)


This uses the insight that the letter in each position of the pattern must be the most common letter corresponding to that position. We can find the letters corresponding to a particular pattern via splitting into pattern-sized groups, and transposing. The main reason this solution is so long is that Jelly doesn't seem to have a short way to find the mode of a list (I made several attempts, but they're all at least six bytes long).

Jelly, 10 bytes, based on @Dennis' solution

⁸ċ$ÞṪ
sZÇ€


Try it online!

This is a combination of @Dennis' solution and my own; there was a five-byte mode in that solution, which I stole for this solution. (I already had solutions based on ⁸ċ, but couldn't get below six bytes with it; I hadn't thought of using Þ.)

Explanation

µ…µ€ and Ç€ (with the … on the previous line) are both three bytes long (the latter needs a newline), and equivalent. Normally I use the former, but the latter's more flexible, as it allows you to use ⁸ to mention the argument.

This makes it possible to sort (Þ) by the number of occurrences in ⁸ (⁸ċ), then take the last element (Ṫ), to find the mode in just five characters.