Given a string s, return the smallest contiguous substring you can remove to create a palindrome.

# Examples:

800233008   -> 2
racecarFOOL -> FOOL
abcdedcba   -> (empty string)
ngryL Myrgn -> "L " (or " M")
123456789   -> 12345678 (or 23456789)
aabcdbaa    -> c (or d)
[[]]        -> [[ (or ]])
a           -> (empty string)


aabaab      -> b    | Suggested by Zgarb, some returned "aa".


# Rules

• Only printable ASCII characters will appear in the input (no newlines, keep it simple).
• Not really a rule, but note <>, /\, (), [] and {} are not palindromes.

This is , smallest byte-count wins.

+100 bounty has been claimed by Adnan

• Tesf case: aabaab Nov 6, 2017 at 17:46
• I think it will help keep questions accessible to more visitors if ingroup jargon like “CMC” is avoided (looking it up, it appears to stand for “chat mini challenge”, which I imagine means a small challenge posted in the chat room associated with this site). Nov 6, 2017 at 20:43
• Isn't [[]] a palindrome?
– Carl
Nov 7, 2017 at 1:46
• @Carl It may look like one, but when you reverse the characters, you get ]][[. Consider that aabb is the same thing, just different characters. Nov 7, 2017 at 3:25
• "(will be awarded 7/12)" huh? Nov 10, 2017 at 9:12

# J, 24 bytes

(0{::(-:|.)\.#&,<\)~i.@#


Try it online!

## Explanation

(0{::(-:|.)\.#&,<\)~i.@#  Input: array of chars S
#  Length of S
i.@   Range, [0, 1, ..., len(S)-1]
(                 )~      Dyadic verb on range and S
\.               For each outfix of S of size x in range
|.                    Reverse
-:                      Matches input (is palindrome)
<\          Box each infix of S of size x in range
#&,            Flatten each and copy the ones that match
0{::                       Fetch the result and index 0 and return

• Perhaps you might want to choose (;&quote f)&> as the test harness verb? Nov 7, 2017 at 3:25

# Jelly, 16 bytes

Ḣ;Ṫµ=Ṛ
0,0jŒṖÇÞṪ


Try it online!

### How it works

0,0jŒṖÇÞṪ  Main link. Argument: s (string)

0,0j       Join [0, 0], separating by s. This prepends and appends a 0 to s.
ŒṖ     Build all partitions of the resulting array.
ÇÞ   Sort the partitions by the helper link.
As a side effect, this will remove the first and last element of each
partition. The 0's make sure that not removing any characters from s
will still remove [0] from both sides.
Ṫ  Tail; extract the last one.

Ḣ;Ṫµ=Ṛ     Helper link. Argument: A (array/partition)

Ḣ          Head; yield and remove the first chunk of A.
Ṫ        Tail; yield and remove the last chunk of A.
µ=Ṛ     Compare the result, character by character, with its reverse.
A palindrome of length l will yield an array of l 1's, while a
non-palindrome of length l will yield an array with at least one 0 among
the first l/2 Booleans. The lexicographically largest result is the one
with the longest prefix of 1's, which corresponds to the longest
palindrome among the outfixes.


## Wolfram Language (Mathematica), 53 51 bytes

Byte count assumes CP-1252 encoding.

±{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:={b}


Try it online!

Defines a unary operator ± (or a function PlusMinus). Input and output are lists of characters. The test suite does the conversion from and to actual strings for convenience.

• Is Reverse then comparing that reverse to the original shorter than PalindromeQ? I don't know Mathematica, so no idea. Nov 6, 2017 at 15:08
• Good answer, but shouldn't one account for the splitting of strings and joining them back together in your character count? Characters@#/.{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:>b~~""& Nov 6, 2017 at 15:08
• @MagicOctopusUrn Reverse[x={a,c}]==x is two bytes longer. I don't know whether there's any shorter alternative. Nov 6, 2017 at 15:11
• @KellyLowder Lists of characters are valid representations of strings on PPCG. It's a bit awkward in Mathematica, where you wouldn't normally use that representation, but it's still valid. I'll dig up a meta post. Nov 6, 2017 at 15:12
• @KellyLowder I think this is the accepted policy. The main reason why it's awkward in Mathematica is that Mathematica doesn't have an actual character type, so the characters end up being singleton strings. Nov 6, 2017 at 15:15

# 05AB1E, 18 bytes

ā<Œ¯¸«ʒRõsǝÂQ}éнèJ


Uses the 05AB1E encoding. Try it online!

• Interesting usage of filter there... We were trying to do an "a without b" type of deal, but if there was two instances of the substring, we'd get false negatives. Feels like we were over-complicating it now that I see this lol. Noice, I'll give you a 100 bounty in 2 days. Nov 6, 2017 at 17:53
• ǝ was seriously genius though. Nov 6, 2017 at 19:40

# Jelly, 20 bytes

ŒḂ⁹Ƥ
çÐ€JN$Ẏi1ịẆẋ⁻Ṛ$


Try it online!

# Python 3, 97 bytes

f=lambda s,p='	':min([s][:p[::-1]in p+p]+(s and[f(s[1:],p+s[0]),f(s[:-1],s[-1]+p)]or[p]),key=len)


Try it online!

# Python 2, 116 bytes

def f(i):R=range(len(i)+1);print min([i[y:k+1]for y in R for k in R if(i[:y]+i[k+1:])[::-1]==i[:y]+i[k+1:]],key=len)


Try it online!

Saved a couple of bytes with help from Halvard Hummel!

• 117 bytes Nov 6, 2017 at 16:12
• @HalvardHummel Thanks, I was planning to change that too but didn’t have an internet connection for the last 2 hours. Nov 6, 2017 at 17:14

# Japt, 26 22 bytes

¬£¬ËUjEY ê¬©UtEY
c æ+0


Test it online! Trying to figure out how to map false to something falsy and any string to something truthy in one byte. Currently I'm using +0...

# Bash, 108 bytes

for((j=0;;j++)){
for((i=0;i<${#1};i++)){ r=${1:0:i}${1:j+i} [[$r = rev<<<$r ]]&&echo "${1:i:j}"&&exit
}
}


Takes input as command-line argument.

Try it online! with quotes printed around the output for viewing leading/trailing spaces.

# Prolog, 271 byte

p([_]).
p([X,X]).
p([X|Y]):-append([P,[X]],Y),p(P).

s(P,M,S,R,N):-p(P),append([M,S],N).
s(P,M,S,S,N):-p(S),append([P,M],N).
s(P,M,S,P,M):-append([P,S],X),p(X).

d(Y,P,N):-
findall([A,B,C],(append([R,M,X],Y),s(R,M,X,B,C),length(B,A)),S),
sort(1,@>,S,[[_,P,N]|_]).


At some point I realized this is going to be huge by code-golf standards, so I kept a few extra blank spaces to preserve the resemblance to the non-obfuscated version. But I still think it might be interesting since it's a different approach to the problem.

The non-obfuscated version:

palindrome([_]).
palindrome([X, X]).
palindrome([X | Xs]) :-
append([Prefix, [X]], Xs),
palindrome(Prefix).

palindrome_split(Prefix, Mid, Suffix, Prefix, N) :-
palindrome(Prefix),
append([Mid, Suffix], N).
palindrome_split(Prefix, Mid, Suffix, Suffix, N) :-
palindrome(Suffix),
append([Prefix, Mid], N).
palindrome_split(Prefix, Mid, Suffix, P, Mid) :-
append([Prefix, Suffix], P),
palindrome(P).

findall(
[La, Pa, Na],
(append([Prefix, Mid, Suffix], NP),
palindrome_split(Prefix, Mid, Suffix, Pa, Na),
length(Pa, La)),
Palindromes),
sort(1, @>, Palindromes, [[_, P, N] | _]).


## C++, 254248 246 bytes

-6 bytes thanks to Zacharý -2 bytes thanks to Toby Speight

#include<string>
#define S size()
#define T return
using s=std::string;int p(s t){for(int i=0;i<t.S;++i)if(t[i]!=t[t.S-i-1])T 0;T 1;}s d(s e){if(!p(e))for(int i,w=1;w<e.S;++w)for(i=0;i<=e.S-w;++i){s t=e;t.erase(i,w);if(p(t))T e.substr(i,w);}T"";}


So...

• I used T as a macro definition because doing R"" as another effect on string literal ( it's a prefix used to define raw string literals, see cppreference for more informations ) that is not there when i do T""
• Preprocessor definitions can't be on the same line, and have to have at least one space between the name and the content in the definition
• 2 functions : p(std::string) to test if the string is a palindrome. If it is, it returns 1 which casts to true, else it returns 0, which casts to false
• The algorithm loops over the whole string testing if it's a palindrome when erasing each time 1 element, then test erasing 2 elements ( loops over that to the maximum size of the string ), from the first index to the last index - number of erased char. If it finds erasing some part is a palindrome, then, it returns. For example, when passing the string "aabcdbaa" as parameter, both c and d are valid answer, but this code will return c because erasing it and testing if it's a palindrome comes before testing if erasing d and testing if it's palindrome
• Here is the code to test :

std::initializer_list<std::pair<std::string, std::string>> test{
{"800233008","2"},
{ "racecarFOOL","FOOL" },
{ "abcdedcba","" },
{ "ngryL Myrgn","L " },
{ "123456789","12345678" },
{ "aabcdbaa","c" },
{ "[[]]","[[" },
{ "a","" },
{ "aabaab","b" }
};

for (const auto& a : test) {
if (a.second != d(a.first)) {
std::cout << "Error on : " << a.first << " - Answer : " << a.second  << " - Current : " << d(a.first) << '\n';
}
}

• Would this work for the last line? using s=std::string;int p(s t){for(int i=0;i<t.S/2;++i)if(t[i]!=t[t.S-i-1])T 0;T 1;}s d(s e){if(!p(e))for(int i,w=1;w<e.S;++w)for(i=0;i<=e.S-w;++i){s t=e;t.erase(i,w);if(p(t))T e.substr(i,w);}T"";} Nov 7, 2017 at 19:19
• Can the /2 be omitted? Iterating over the whole length will simply repeat the tests we've done, which should be harmless. You might want to expand what you mean by the "other effect" of R"" (i.e. it's parsed as a raw string literal). Nov 8, 2017 at 11:20
• I've modified this and added the result as an answer of my own. Nov 8, 2017 at 12:12

# Jelly, 33 bytes

r/ḟ@J}ị
“”µJpç³$ŒḂ$Ðfạ/ÞḢr/ịµŒḂ?


Try it online!

# PHP 104+1 bytes

while(~($s=$argn)[$e+$i++]?:++$e|$i=0)strrev($t=substr_replace($s,"",$i,$e))==$t&&die(substr($s,$i,$e));


Run as pipe with -nR or try it online.

snd.minimum.([]#)
p#s@(a:b)=[(i,take i s)|i<-[0..length s],(==)<*>reverse$p++drop i s]++(p++[a])#b p#_=[]  Try it online! EDIT: Thanks @H.PWiz for taking off 4 bytes! I need to get better with those monads! # JavaScript, 90 bytes a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k  Try it online! f= a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k F=a=>console.log(a.padEnd(11)+' ---> '+f([...a]).join) F('800233008') F('racecarFOOL') F('abcdedcba') F('ngryL Myrgn') F('123456789') F('aabcdbaa') F('[[]]') F('a') F('aabaab') # Perl 5, 72 +1 (-p) bytes $\=$_;/.*(?{$,=$.$';$\=$&if length$&<length$\&&$,eq reverse$,})(?!)/g}{


Try it online

# JavaScript (ES6), 91 78 bytes

(s,i=0,j=0,S=[...s],b=S.splice(i,j))=>S+''==S.reverse()?b:f(s,s[++i]?i:!++j,j)


Input and output are lists of characters.

Recursively removes a larger and larger slice from the input until a palindrome is found.

Snippet:

f=
(s,i=0,j=0,S=[...s],b=S.splice(i,j))=>S+''==S.reverse()?b:f(s,s[++i]?i:!++j,j)

console.log(f([...'800233008']).join)   // 2
console.log(f([...'racecarFOOL']).join) // FOOL
console.log(f([...'abcdedcba']).join)   // (empty string)
console.log(f([...'ngryL Myrgn']).join) // "L " (or " M")
console.log(f([...'123456789']).join)   // 12345678 (or 23456789)
console.log(f([...'aabcdbaa']).join)    // c (or d)
console.log(f([...'[[]]']).join)        // [[ (or ]])
console.log(f([...'a']).join)           // (empty string)

# TSQL (2016) 349B

Not the most compact but straightforward solution:

DECLARE @i VARCHAR(255)='racecarFOOL'
;WITH DAT(v,i,l)AS(SELECT value,(ROW_NUMBER()OVER(ORDER BY value))-1,LEN(@i)FROM STRING_SPLIT(REPLICATE(@i+';',LEN(@i)+1),';')WHERE value<>'')
SELECT TOP 1C,S
FROM(SELECT LEFT(D.v, D.i)+SUBSTRING(D.v,D.i+E.i+1,D.l)C,SUBSTRING(D.v,D.i+1,E.i)S
FROM DAT D CROSS APPLY DAT E)C
WHERE C=REVERSE(C)
ORDER BY LEN(C)DESC

• You can use @ as a variable for a few bytes. In the CTE you can use where''=value) for another one and you don't need to return C in the result. Nov 12, 2017 at 19:44

# Husk, 18 bytes

◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰


Try it online!

## Explanation

◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰  Input is a string, say s="aab"
ŀ⁰    Indices of s: x=[1,2,3]
Q      Slices: [[],[1],[1,2],[2],[1,2,3],[2,3],[3]]
ṠM-       Remove each from x: [[1,2,3],[2,3],[3],[1,3],[],[1],[1,2]]
†!⁰          Index into s: ["aab","ab","b","ab","","a","aa"]
mS=↔             Check which are palindromes: [0,0,1,0,1,1,1]
f             Q⁰  Filter the slices of s by this list: ["aa","aab","ab","b"]
◄L                  Minimum on length: "b"


""#0
(h#n)t|(==)=<<reverse$h++drop n t=take n t|x:r<-t=(h++[x])#n$r|m<-n+1=t#m$h  Try it online! Example usage: ""#0$ "aabaab" yields "b".

Edit: -1 byte thanks to Ørjan Johansen.

• You can replace the last "" by t. Nov 11, 2017 at 18:22

# C++, 189186176 167 bytes

I started with HatsuPointerKun's answer, changing the test to simply compare equality with reversed string; then I changed how we enumerate the candidate strings. Following this, the macros were only used once or twice each, and it was shorter to inline them.

#include<string>
using s=std::string;s d(s e){for(int i,w=0;;++w){s t=e.substr(w);for(i=-1;++i<=t.size();t[i]=e[i])if(t==s{t.rbegin(),t.rend()})return e.substr(i,w);}}


## Explanation

std::string downgrade(std::string e)
{
for (int w=0; ; ++w) {
std::string t = e.substr(w);
for (int i=0;  i<=t.size();  ++i) {
if (t == std::string{t.rbegin(),t.rend()})
// We made a palindrome by removing w chars beginning at i
return e.substr(i,w);
t[i] = e[i];  // next candidate
}
}
}


The enumeration of candidates begins by initialising a string with the first w characters omitted, and then copying successive characters from the original to move the gap. For example, with the string foobar and w==2:

foobar
↓↓↓↓
obar

foobar
↓
fbar

foobar
↓
foar

foobar
↓
foor

foobar
↓
foob


The first pass (with w==0) is a no-op, so the full string will be considered over and over again. That's fine - golfing trumps efficiency! The last iteration of this loop will access the one-past-the-end index; I seem to get away with that with GCC, but strictly, that's Undefined Behaviour.

## Test program

A direct lift from HatsuPointerKun's answer:

static const std::initializer_list<std::pair<std::string, std::string>> test{
{ "800233008", "2" },
{ "racecarFOOL", "FOOL" },
{ "abcdedcba", "" },
{ "ngryL Myrgn", "L " },
{ "123456789", "12345678" },
{ "aabcdbaa", "c" },
{ "[[]]", "[[" },
{ "a","" },
{ "aabaab", "b" }
};

#include <iostream>
int main()
{
for (const auto& a : test) {
if (a.second != d(a.first)) {
std::cout << "Error on: " << a.first
<< " - Expected: " << a.second
<< " - Actual: " << d(a.first) << '\n';
}
}
}


## REXX, 132 bytes

a=arg(1)
l=length(a)
do i=1 to l
do j=0 to l-i+1
b=delstr(a,i,j)
if b=reverse(b) & m>j then do
m=j
s=substr(a,i,j)
end
end
end
say s


# Ruby, 86 84 bytes

->s{l=i=0
(l+=(i+=1)/z=s.size-l+1
i%=z)while(w=s[0,i]+s[i+l..-1])!=w.reverse
s[i,l]}


Try it online!

• Saved 2 bytes thanks to Cyoce
• You don't need the parentheses around z=s.size-l+1. Nov 6, 2017 at 22:29
• @Cyoce Thank you. I have a hard time remembering all the operator precedence. Nov 8, 2017 at 17:58

# C (gcc), 307 bytes

#define T malloc(K)
P(S,i,y,z,k,u,L,K,V)char*S;{char*M,*R,*E;K=strlen(S);M=T;R=T;E=T;for(i=0;i<K;++i){for(y=0;y<=K-i;++y){strcpy(M,S);for(z=y;z<y+i;E[z-y]=M[z],++z);for(k=y;k+i<=K;M[k]=M[k+i],++k);V=strlen(M);strcpy(R,M);for(u=0;u<V/2;L=R[u],R[u]=R[V-u-1],R[V-u-1]=L,++u);if(!strcmp(M,R))puts(E),exit(0);}}}


Try it online!