33
4
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 -> Valid outputs
1 a -> a
1 aa -> a
2 aa -> aa
1 ab -> a b
2 ab -> ab
1 abb -> b
2 abb -> ab bb
2 ababa -> ab
2 abcba -> ab
2 aabbbbb -> bb (ab is not a valid output here)
3 aababba -> aab abb
3 aababbaa -> aab
3 asdasfadf -> asf
3 asdasfadfsdf -> asf adf
2 abcdefghijklmnopqrstuvwxyzyx -> yx
2 supercalifragilisticexpialidocious -> ic ii
3 supercalifragilisticexpialidocious -> iri ili ioi
4 supercalifragilisticexpialidocious -> scii
5 supercalifragilisticexpialidocious -> iapic
2 eeeebaadbaecaebbbbbebbbbeecacebdccaecadbbbaceebedbbbddadebeddedbcedeaadcabdeccceccaeaadbbaecbbcbcbea -> bb be
10 bbbbacacbcedecdbbbdebdaedcecdabcebddbdcecebbeeaacdebdbebaebcecddadeeedbbdbbaeaaeebbedbeeaeedadeecbcd -> ebbbdbeece ebdbdbeece
20 aabbbaaabaaabaaaabbbbabbbbabbbabbbbbabbaaaababbbaababbbaababaaaabbaaabbaabbbabaaabbabbaaabbaaaaaaaba -> 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.
2This challenge is Zgarb-quality. Nice work! – Martin Ender – 2017-03-22T16:39:47.650
I'm assuming only trailing characters are ignored? So you aren't allowed to ignore leading characters like this:
2 abb -> ba
where it's built up as(b)[ab]a
: leading(b)
is ignored,[ab]
are matching. – Kevin Cruijssen – 2017-03-23T10:50:13.673@KevinCruijssen Right, the pattern must start repeating at the beginning. – ETHproductions – 2017-03-23T12:05:01.990