Получив строку s, верните наименьшую непрерывную подстроку, которую вы можете удалить, чтобы создать палиндром.

Примеры:

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

правила

• На входе будут отображаться только печатные символы ASCII (без перевода строки, будьте проще).
• Не совсем правило, но заметьте <>, /\, (), []и {}не палиндромов.

Это код-гольф , выигрывает самый маленький счетчик байтов.

Аднан потребовал +100 к награде

Желе , 16 байт

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

Попробуйте онлайн!

Как это устроено

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 байта

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

Попробуйте онлайн!

объяснение

(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 байт

Подсчет байтов предполагает кодирование CP-1252.

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

Попробуйте онлайн!

Определяет унарный оператор ±(или функцию PlusMinus). Ввод и вывод - это списки символов. Набор тестов выполняет преобразование из и в фактические строки для удобства.

Желе , 20 байт

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

Попробуйте онлайн!

05AB1E , 18 байт

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

Использует кодировку 05AB1E . Попробуйте онлайн!

Python 3 , 97 байт

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)

Попробуйте онлайн!

Python 2 , 116 байт

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)

Попробуйте онлайн!

Спасли пару байтов с помощью Халварда Хаммеля !

Japt , 26 22 байта

¬£¬ËUjEY ꬩUtEY
c æ+0

Проверьте это онлайн! Попытка выяснить, как сопоставить falseчто-то ложное и любую строку с чем-то правдивым в одном байте В настоящее время я использую +0...

Баш , 108 байт

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

Принимает ввод в качестве аргумента командной строки.

Попробуйте онлайн! с кавычками, напечатанными вокруг выхода для просмотра начальных / конечных пробелов.

Пролог , 271 байт

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

В какой-то момент я понял, что это будет огромным по стандартам code-golf, поэтому я оставил несколько лишних пробелов, чтобы сохранить сходство с неясной версией. Но я все еще думаю, что это может быть интересно, так как это другой подход к проблеме.

Не запутанная версия:

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 байт

-6 байтов благодаря Захарию -2 байта благодаря Тоби Спейту

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

Так...

• Я использовал Tв качестве определения макроса, потому что он выполняет R""еще один эффект для строкового литерала (это префикс, используемый для определения необработанных строковых литералов, см. Cppreference для получения дополнительной информации), которого нет, когда яT""
• Определения препроцессора не могут быть в одной строке и должны иметь хотя бы один пробел между именем и содержимым в определении
• 2 функции: p(std::string)проверить, является ли строка палиндромом. Если это так, он возвращает то, 1что приводит, в trueпротивном случае возвращает 0, который приводит кfalse
• Алгоритм проходит по всей строке, проверяя, является ли палиндром, стирая каждый раз по 1 элементу, затем проверяя стирание 2 элементов (повторяет это до максимального размера строки), от первого индекса до the last index - number of erased char. Если он обнаруживает, что стирание какой-либо части является палиндромом, он возвращается. Например, при передаче строки в "aabcdbaa"качестве параметра оба cи dявляются допустимым ответом, но этот код вернется, cпотому что его удаление и проверка, если это палиндром, предшествуют проверке, если стирание, dи тестирование, если это палиндром.

• Вот код для тестирования:

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

Желе , 33 байта

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

Попробуйте онлайн!

PHP 104 + 1 байт

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

Запустите как трубу с -nRили попробуйте онлайн .

Haskell , 109 105 байт

snd.minimum.([]#)
p#s@(a:b)=[(i,take i s)|i<-[0..length s],(==)<*>reverse$p++drop i s]++(p++[a])#b
p#_=[]

Попробуйте онлайн!

РЕДАКТИРОВАТЬ: Спасибо @ H.PWiz за удаление 4 байта! Мне нужно поправиться с этими монадами!

JavaScript, 90 байт

a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k

Попробуйте онлайн!

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) байтов

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

Попробуйте онлайн

JavaScript (ES6), 91 78 байт

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

Ввод и вывод - это списки символов.

Рекурсивно удаляет все больший и больший срез со входа, пока не будет найден палиндром.

Отрывок:

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

Не самое компактное, но простое решение:

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

Шелуха , 18 байт

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

Попробуйте онлайн!

объяснение

◄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 байт

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

Попробуйте онлайн! Пример использования: ""#0 $ "aabaab"доходность "b".

Редактировать: -1 байт благодаря Эрджану Йохансену.

C ++, 189 186 176 167 байт

Я начал с ответа HatsuPointerKun , изменив тест, чтобы просто сравнить равенство с перевернутой строкой; затем я изменил способ перечисления строк-кандидатов. После этого макросы использовались только один или два раза, и их было короче.

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

объяснение

Эквивалентный читаемый код:

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

Перечисление кандидатов начинается с инициализации строки с wпропущенными первыми символами, а затем копирования последовательных символов из оригинала для перемещения пробела. Например, со строкой foobarи w== 2:

foobar
  ↓↓↓↓
  obar

foobar
↓
fbar

foobar
 ↓
foar

foobar
  ↓
foor

foobar
   ↓
foob

Первый проход (с w== 0) является запретом, поэтому полная строка будет рассматриваться снова и снова. Это хорошо - игра в гольф превосходит эффективность! Последняя итерация этого цикла будет обращаться к индексу «один за другим»; Мне кажется, что это сходит с рук с GCC, но строго говоря, это неопределенное поведение.

Тестовая программа

Прямой ответ от ответа ХацуПоинтерКуна :

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 байта

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

Рубин , 86 84 байта

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

Попробуйте онлайн!

• Сохранено 2 байта благодаря Cyoce

C (gcc) , 307 байтов

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

Попробуйте онлайн!