# Stitch Together a Palindrome from Palindromic Substrings

Given a string l, find all palindromic substrings p of l (including duplicates and single character strings). Next, rearrange all sub-strings in p into a valid palindrome (there may be multiple correct answers). If it is not possible to rearrange p into a single palindrome, your program may have undefined behavior (error, stack-overflow, exiting, hanging/untimely murder of John Dvorak, etc...)

# Examples

## Valid Test Cases

l = anaa
p = ['a', 'n', 'a', 'a', 'aa', 'ana']
result = anaaaaana or aanaaanaa or aaananaaa

l = 1213235
p = ['1', '2', '1', '3', '2', '3', '5', '121', '323']
result = 1213235323121

l = racecar
p = ['r', 'a', 'c', 'e', 'c', 'a', 'r', 'cec', 'aceca', 'racecar']
result = racecarcecaacecracecar (there are others)

l = 11233
p = ['1', '11', '1', '2', '3', '33', '3']
result = 113323311 or 331121133

l = abbccdd
p = ['a', 'b', 'bb', 'b', 'c', 'cc', 'c', 'd', 'dd', 'd']

l = a
p = ['a']
result = a


## Invalid Test Cases (Not Possible)

l = 123456789
p = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
result = <not possible, behavior undefined>

l = hjjkl
p = ['h', 'j', 'jj', 'j', 'k', 'l']
result = <not possible, behavior undefined>

l = xjmjj
p = ['x', 'j', 'jmj', 'm', 'j', 'jj', 'j']
result = <not possible, behavior undefined>


# Rules

• If the input word is a palindrome itself, it will always be valid as input.
• Only one substring should be returned, which one you choose is arbitrary as long as it's valid.
• If the input has no viable output, your code may have undefined behavior.
• Inputs will only contain ASCII-Printable characters between 0x20-0x7E.
• This is , lowest byte-count is the winner.
• The first proposed result for "abbccdd" is wrong: the last two letters should be "bb", not "dd". Feb 13, 2018 at 15:47
• Can we return an array of substrings, rather than a single string? Feb 13, 2018 at 17:54
• Can I take a list of characters as input? Feb 14, 2018 at 1:49
• By hanging being acceptable behavior, do you mean hanging the person who gave it input? Feb 14, 2018 at 8:35
• @JohnDvorak clarified. Feb 14, 2018 at 16:52

# Brachylog, 10 bytes

{s.↔}ᶠpc.↔


Try it online!

Fails (i.e. prints false.) if not possible.

### Explanation

{   }ᶠ         Find all…
s.              …substrings of the input…
.↔             …which are their own reverse
p        Take a permutation of this list of palindromes
c.      The output is the concatenation of this permutation
.↔     The output is its own reverse


# Coconut, 140 bytes

s->p(map(''.join,permutations(p(v for k in n(s)for v in n(k[::-1])))))
from itertools import*
n=scan$((+)) p=list..filter$(x->x==x[::-1])


Try it online!

# JavaScript (ES6), 193 bytes

"Look Ma, no permutation built-in!" (So yes ... it's long ...)

Returns an empty array if there's no solution.

f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join)||S


### Demo

f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join)||S

console.log(f('anaa'))
console.log(f('1213235'))
console.log(f('hjjkl'))
console.log(f('a'))

### How?

Let's split the code into smaller parts.

We define P(), a function that returns s if s is a palindrome, or false otherwise.

P = s => [...s].reverse().join == s && s


We compute all substrings of the input string s. Using P(), we isolate the non-empty palindromes and store them in the array a.

a = [].concat(...[...s].map((_, i, a) => a.map((_, j) => s.slice(i, j + 1)))).filter(P)


The main recursive function f() takes a as input and compute all its permutations. It updates S whenever the permutation itself is a palindrome (once joined), and eventually returns the final value of S.

f = (                        // given:
a,                         //   a[] = input array
m = S = []                 //   m[] = current permutation of a[]
) =>                         //   and S initialized to []
S = a.map((_, i) =>        // for each element at position i in a[]:
f(                       //   do a recursive call with:
b = [...a],            //     b[] = copy of a[] without the i-th element
[...m, b.splice(i, 1)] //     the element extracted from a[] added to m[]
)                        //   end of recursive call
) > '' ?                   // if a[] was not empty:
S                        //   let S unchanged
:                          // else:
P(m.join) || S         //   update S to m.join('') if it's a palindrome


# Jelly, 13 bytes

ŒḂÐf
ẆÇŒ!F€ÇḢ


Try it online!

Prints 0 in the invalid case.

# Stax, 13 bytes

ç»¬►Ö∞j∞:Æ╘τδ


Run test cases (It takes about 10 seconds on my current machine)

This is the corresponding ascii representation of the same program.

:e{cr=fw|Nc$cr=!  It's not quite pure brute-force, but it's just as small as the brute-force implementation I wrote. That one crashed my browser after about 10 minutes. Anyway, here's how it works. :e Get all contiguous substrings {cr=f Keep only those that are palindromes w Run the rest of the program repeatedly while a truth value is produced. |N Get the next permutation. c$        Copy and flatten the permutation.
cr=!    Test if it's palindrome.  If not, repeat.
The last permutation produced will be implicitly printed.


# Ruby, 131123 120 bytes

->s{m=->t{t==t.reverse}
(1..z=s.size).flat_map{|l|(0..z-l).map{|i|s[i,l]}}.select(&m).permutation.map(&:join).detect &m}


Try it online!

A lambda accepting a string and returning a string. Returns nil when no solution exists.

-5 bytes: Replace select{|t|l[t]} with select(&l)

-3 bytes: Replace map{..}.flatten with flat_map{...}

-1 bytes: Loop over substring length and substring start, instead of over substring start and substring end

-2 bytes: Declare z at first use instead of beforehand

->s{
l=->t{t==t.reverse}        # Lambda to test for palindromes
(1..z=s.size).flat_map{|l| # For each substring length
(0..z-l).map{|i|         # For each substring start index
s[i,l]                 # Take the substring
}
}                          # flat_map flattens the list of lists of substrings
.select(&l)                # Filter to include only palindromic substrings
.permutation               # Take all orderings of substrings
.map(&:join)               # Flatten each substring ordering into a string
.detect &l                 # Find the first palindrome
}


# 05AB1E, 13 12 bytes

ŒʒÂQ}œJʒÂQ}¤


Try it online!

-1 byte thanks to Magic Octopus Urn and Emigna.

• J automatically factorizes so you don't need €J just J; also, you're supposed to return one of the palindromes, not all. Try it online! is valid for the same byte-count. Feb 13, 2018 at 15:49
• @MagicOctopusUrn Fixed, thanks ! Feb 13, 2018 at 15:53
• Ùć could be ¤ (or a number of other options) Feb 13, 2018 at 17:26
• @Emigna not sure why I didn't see the Ù wasn't needed. Feb 13, 2018 at 17:44
• Enigma My bad, for an unknown reason I thought we were supposed to display all of the unique palindromes, hence the original Ù. Thanks for the tip, fixed ! Feb 14, 2018 at 9:24

# Pyth, 13 bytes

h_I#sM.p_I#.:


Try it online!

-1 byte thanks to Mr. Xcoder

• Lol I was so sure nobody else uses Pyth that I submitted my own separate answer (now deleted) prior to seeing yours. You can use h_I#sM.p_I#.: or e_IDsM.p_I#.: for 13 bytes. Feb 13, 2018 at 16:25
• @Mr.Xcoder Oh haha :P yeah I hardly ever use Pyth, don't know why I decided to use it. Thanks! Feb 13, 2018 at 16:51

# Python 3, 167 bytes

lambda a:g(sum(k,[])for k in permutations(g(a[i:j+1]for i in range(len(a))for j in range(i,len(a)))))
g=lambda k:[e for e in k if e==e[::-1]]
from itertools import*


Try it online!

-2 bytes thanks to Mr. Xcoder

• You can use a[i:j+1] if you then use for j in range(i,len(a)) instead, for -2 bytes. Feb 13, 2018 at 16:41

# Japt, 19 bytes

Hampered by Japt not (yet) being able to get all substrings of a string (and partly by my current levels of exhaustion!).

Outputs undefined if there's no solution.

Êõ@ãX fêQÃc á m¬æêQ


Try it

## Explanation

                        :Implicit input of string U
Ê                       :Length of U
õ                      :Range [1,Ê]
@      Ã              :Pass each X through a function
ãX                   :  Substrings of U of length X
f                 :  Filter
êQ               :    Is it a palindrome?
c             :Flatten
á           :Permutations
m         :Map
¬        :  Join to a string
æêQ     :Get first element that is a palindrome

• Is your question about a list of substring simply to remove ¬ from your answer :P? Feb 13, 2018 at 18:37
• Thought I could remove m¬ but then I would have needed æ_¬êQ so it wouldn't have saved any bytes anyway! Feb 13, 2018 at 20:13
• Hahaha, I'll ensure to be wary of your byte-saving ways from now on ;). I tried removing it myself to check, but realized japt commands don't work like I think they work lol. Feb 13, 2018 at 20:28

# Husk, 12 bytes

ḟS=↔mΣPfS=↔Q


Try it online!

## Explanation

ḟS=↔mΣPfS=↔Q  Implicit input, a string.
Q  List of substrings.
f      Keep those
S=↔   that are palindromic (equal to their reversal).
P       Permutations of this list.
mΣ        Flatten each.
ḟ             Find an element
S=↔          that is palindromic.


# J, 53 bytes

[:{:@(#~b"1)@(i.@!@#;@A.])@(#~(0<#*b=.]-:|.)&>)@,<\\.


Try it online!