Dada uma sequência s, retorne a menor substring contígua que você pode remover para criar um palíndromo.

Exemplos:

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

Sugestões de casos de teste dos usuários (se você encontrar um caso de borda não listado, poste um comentário):

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

Regras

• Somente caracteres ASCII imprimíveis aparecerão na entrada (sem novas linhas, mantenha-o simples).
• Não é realmente uma regra, mas nota <>, /\, (), []e {}não são palíndromos.

Este é o código-golfe , o menor número de bytes ganhos.

+100 recompensa foi reivindicada por Adnan

Gelatina , 16 bytes

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

Experimente online!

Como funciona

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.

J , 24 bytes

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

Experimente online!

Explicação

(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

Wolfram Language (Mathematica) , 53 51 bytes

A contagem de bytes assume a codificação CP-1252.

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

Experimente online!

Define um operador unário ±(ou uma função PlusMinus). Entrada e saída são listas de caracteres. O conjunto de testes faz a conversão de e para seqüências reais por conveniência.

Gelatina , 20 bytes

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

Experimente online!

05AB1E , 18 bytes

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

Usa a codificação 05AB1E . Experimente 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)

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

Experimente online!

Salvei alguns bytes com a ajuda de Halvard Hummel !

Japonês , 26 22 bytes

¬£¬ËUjEY ꬩUtEY
c æ+0

Teste online! Tentando descobrir como mapear falsepara algo falso e qualquer string para algo verdadeiro em um byte. Atualmente estou usando +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
}
}

Recebe entrada como argumento da linha de comando.

Experimente online! com aspas impressas ao redor da saída para visualizar espaços à esquerda / à direita.

Prolog , 271 bytes

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

Em algum momento, percebi que isso seria enorme para os padrões do código-golfe, então guardei alguns espaços em branco extras para preservar a semelhança com a versão não ofuscada. Mas ainda acho que pode ser interessante, pois é uma abordagem diferente para o problema.

A versão não ofuscada:

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

C ++, 254 248 246 bytes

-6 bytes graças a Zacharý -2 bytes graças a 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"";}

Assim...

• Eu usei Tcomo uma definição de macro porque fazer R""como outro efeito no literal de cadeia (é um prefixo usado para definir literais de cadeia brutos, consulte cppreference para obter mais informações) que não existe quando eu façoT""
• As definições de pré-processador não podem estar na mesma linha e precisam ter pelo menos um espaço entre o nome e o conteúdo na definição
• 2 funções: p(std::string)para testar se a sequência é um palíndromo. Se for, retorna para 1qual lança true, caso contrário, retorna para 0qual lançafalse
• O algoritmo faz um loop ao longo de todo o teste de cadeia de caracteres, se for um palíndromo ao apagar cada elemento de 1 vez; em seguida, teste o apagamento de 2 elementos (faz um loop desse tamanho até o tamanho máximo da cadeia de caracteres), do primeiro índice para the last index - number of erased char. Se achar que apagar alguma parte é um palíndromo, ele retornará. Por exemplo, ao passar a string "aabcdbaa"como parâmetro, tanto ce dsão a resposta válida, mas este código irá retornar cporque apagá-lo e testar se é um palíndromo vem antes de testar se apagando de testando se é palíndromo

• Aqui está o código para testar:

  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';
      }
  }

Gelatina , 33 bytes

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

Experimente 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));

Execute como pipe -nRou experimente online .

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#_=[]

Experimente online!

EDIT: Obrigado @ H.PWiz por decolar 4 bytes! Eu preciso melhorar com essas mônadas!

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

Experimente 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}{

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

Entrada e saída são listas de caracteres.

Remove recursivamente uma fatia cada vez maior da entrada até que um palíndromo seja encontrado.

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

Não é a solução mais compacta, mas direta:

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

Casca , 18 bytes

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

Experimente online!

Explicação

◄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"

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

Experimente online! Exemplo de uso: ""#0 $ "aabaab"rendimentos "b".

Edit: -1 byte graças a Ørjan Johansen.

C ++, 189 186 176 167 bytes

Comecei com a resposta de HatsuPointerKun , alterando o teste para simplesmente comparar igualdade com string invertida; então mudei como enumeramos as cadeias de candidatos. Depois disso, as macros eram usadas apenas uma ou duas vezes cada, e era mais curto para incorporá-las.

#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);}}

Explicação

Código legível equivalente:

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

A enumeração de candidatos começa inicializando uma sequência com os primeiros wcaracteres omitidos e copiando caracteres sucessivos do original para mover a lacuna. Por exemplo, com a sequência foobare w== 2:

foobar
  ↓↓↓↓
  obar

foobar
↓
fbar

foobar
 ↓
foar

foobar
  ↓
foor

foobar
   ↓
foob

A primeira passagem (com w== 0) é no-op; portanto, a sequência completa será considerada repetidamente. Tudo bem - o golfe supera a eficiência! A última iteração desse loop acessará o índice one-past-the-end; Parece que me dou bem com o GCC, mas estritamente esse é um comportamento indefinido.

Programa de teste

Um levantamento direto da resposta de HatsuPointerKun :

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]}

Experimente online!

• Guardado 2 bytes graças a Cyoce

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);}}}

Experimente online!