47
\$\begingroup\$

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)

Test case suggestions from users (if you find an edge case not listed, please post a comment):

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

\$\endgroup\$
  • 3
    \$\begingroup\$ Tesf case: aabaab \$\endgroup\$ – Zgarb Nov 6 '17 at 17:46
  • 14
    \$\begingroup\$ 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). \$\endgroup\$ – ShreevatsaR Nov 6 '17 at 20:43
  • \$\begingroup\$ Isn't [[]] a palindrome? \$\endgroup\$ – Carl Nov 7 '17 at 1:46
  • 4
    \$\begingroup\$ @Carl It may look like one, but when you reverse the characters, you get ]][[. Consider that aabb is the same thing, just different characters. \$\endgroup\$ – Conor O'Brien Nov 7 '17 at 3:25
  • 1
    \$\begingroup\$ "(will be awarded 7/12)" huh? \$\endgroup\$ – Erik the Outgolfer Nov 10 '17 at 9:12

24 Answers 24

8
\$\begingroup\$

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.
 ;         Concatenate head and tail.
   µ=Ṛ     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.
\$\endgroup\$
10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Perhaps you might want to choose (;&quote f)&> as the test harness verb? \$\endgroup\$ – Conor O'Brien Nov 7 '17 at 3:25
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is Reverse then comparing that reverse to the original shorter than PalindromeQ? I don't know Mathematica, so no idea. \$\endgroup\$ – Magic Octopus Urn Nov 6 '17 at 15:08
  • \$\begingroup\$ 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~~""& \$\endgroup\$ – Kelly Lowder Nov 6 '17 at 15:08
  • \$\begingroup\$ @MagicOctopusUrn Reverse[x={a,c}]==x is two bytes longer. I don't know whether there's any shorter alternative. \$\endgroup\$ – Martin Ender Nov 6 '17 at 15:11
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Nov 6 '17 at 15:12
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Nov 6 '17 at 15:15
5
\$\begingroup\$

Jelly, 20 bytes

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

Try it online!

\$\endgroup\$
5
+100
\$\begingroup\$

05AB1E, 18 bytes

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

Uses the 05AB1E encoding. Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Magic Octopus Urn Nov 6 '17 at 17:53
  • \$\begingroup\$ ǝ was seriously genius though. \$\endgroup\$ – Magic Octopus Urn Nov 6 '17 at 19:40
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 117 bytes \$\endgroup\$ – Halvard Hummel Nov 6 '17 at 16:12
  • \$\begingroup\$ @HalvardHummel Thanks, I was planning to change that too but didn’t have an internet connection for the last 2 hours. \$\endgroup\$ – Mr. Xcoder Nov 6 '17 at 17:14
2
\$\begingroup\$

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...

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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).

palindrome_downgrade(NP, P, N):-
    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] | _]).
\$\endgroup\$
2
\$\begingroup\$

C++, 254 248 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';
        }
    }
    
\$\endgroup\$
  • \$\begingroup\$ 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"";} \$\endgroup\$ – Zacharý Nov 7 '17 at 19:19
  • \$\begingroup\$ 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). \$\endgroup\$ – Toby Speight Nov 8 '17 at 11:20
  • \$\begingroup\$ I've modified this and added the result as an answer of my own. \$\endgroup\$ – Toby Speight Nov 8 '17 at 12:12
1
\$\begingroup\$

Jelly, 33 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 109 105 bytes

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!

\$\endgroup\$
1
\$\begingroup\$

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')

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 72 +1 (-p) bytes

$\=$_;/.*(?{$,=$`.$';$\=$&if length$&<length$\&&$,eq reverse$,})(?!)/g}{

Try it online

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – MickyT Nov 12 '17 at 19:44
1
\$\begingroup\$

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"
\$\endgroup\$
1
\$\begingroup\$

Haskell, 98 94 81 80 bytes

""#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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace the last "" by t. \$\endgroup\$ – Ørjan Johansen Nov 11 '17 at 18:22
1
\$\begingroup\$

C++, 189 186 176 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

Equivalent readable code:

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';
        }
    }
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You don't need the parentheses around z=s.size-l+1. \$\endgroup\$ – Cyoce Nov 6 '17 at 22:29
  • \$\begingroup\$ @Cyoce Thank you. I have a hard time remembering all the operator precedence. \$\endgroup\$ – iamnotmaynard Nov 8 '17 at 17:58
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.