Question

Sometimes a string has buried palindromes in it:

hallolilah contains lol.

And if we took out lol, we'd be left with halilah...which is another palindrome.

Write a program/function that returns the minimum letters left over after repeatedly removing palindromes of at least 3 letters.

Possibly the order in which palindromes are removed affects the number of letters remaining, hence "minimum".

Input

A string of lowercase letters.

Output

A string of leftover lowercase letters.

Scoring

Code golf

Sample data

bazookabambino => bazookmbino

bamalamacocob => `` (empty string)

boofrooracecarnaanoorfood => bd

gogogogogogogogogonow => w

nopalindromesinthisone => nopalindromesinthisone

canacandothecancan => cadothecancan or andothecancan

acaaaab => b

Answer 1

Nekomata, 14 bytes

?{;;$?=t??,}a?

Attempt This Online!

Extremely slow for long inputs that contain many palindromes.

?{;;$?=t??,}a?
?{         }      Loop until failure
  ;;                Split the input into three parts
    $?=             Check that the second part is a palindrome
       t?           Check that the second part has length >= 3
         ?,         If so, join the first and third parts; otherwise fail
            a?    Find the shortest possible solution

If there are multiple shortest solutions, Nekomata will print all of them. You can add the -1 flag to only print the first one.

Answer 2

JavaScript (ES6), 118 bytes

I/O format: arrays of characters.

f=(s,_=o=s)=>s.map((n,i)=>s.map(_=>(q=[...s],p=q.splice(i,n=-~n))[2]&&p+""==p.reverse()&&f(q,0)),s[o.length]?0:o=s)&&o

Try it online!

Commented

f = (               // f is a recursive function taking:
  s,                //   s[] = input
  _ = o = s         //   o[] = output, initialized to the input
) =>                //
s.map((n, i) =>     // for each character at index i in s[],
                    // with n zero'ish:
  s.map(_ =>        //   for each character in s[]:
    (               //
      q = [...s],   //     q[] = copy of s[]
      p = q.splice( //     p[] = palindrome candidate
        i,          //       extracted from q[] at index i
        n = -~n     //       with a length of (at most) n
      )             //       where n is incremented
    )[2] &&         //     if p[] is at least 3 characters long
    p + "" ==       //     and is a palindrome, i.e. it's equal
    p.reverse() &&  //     to its reversed form:
      f(q, 0)       //       do a recursive call with q[]
                    //       (the 2nd argument is here only
                    //       to leave o[] unchanged)
  ),                //   end of inner map()
  s[o.length] ?     //   if s[] is longer than o[]:
    0               //     do nothing
  :                 //   else:
    o = s           //     update o[] to s[]
) && o              // end of outer map(); return o[]

Answer 3

Python3, 233 bytes

def f(s):
 q,r,S=[s],[],[s]
 for s in q:
  if[]==(o:=[(i,j)for i in range(len(s))for j in range(i+1,len(s)+1)if s[i:j]==s[i:j][::-1]and j-i>2]):r+=[s]
  for i,j in o:
   if(U:=s[:i]+s[j:])not in S:S+=[U];q+=[U]
 return min(r,key=len)

Try it online!

Answer 4

Retina, 83 bytes

+%/(.)+(.)\2?(?<-1>\1)+(?(1)^)/&L$w`(.)+(.)\2?(?<-1>\1)+(?(1)^)
$`$'
O#$`
$.&
L`^.*

Try it online! Link includes faster1 test cases. Explanation:

+%/(.)+(.)\2?(?<-1>\1)+(?(1)^)/&`

Repeat on those lines that contain a palindrome...

L$w`(.)+(.)\2?(?<-1>\1)+(?(1)^)

... for all overlapping matches...

$`$'

... remove the match to give the resulting line.

O#$`
$.&

Sort the lines in ascending order of length.

L`^.*

Output only the first (i.e. shortest) line.

1gogogogogogogogogonow is too slow for the w style of overlapping match but the v style also happens to work in this case within TIO's time limit.

Answer 5

C64 Basic, 210 bytes

0inputa$
1l=len(a$):i=1:j=l:ifl<3tH8
2ifmI(a$,i,1)=mI(a$,j,1)tHm=i+1:n=j-1:gO5
3j=j-1:ifj=i+1tHi=i+1:j=l:ifi=l-1tH8
4gO2
5ifm>=ntHa$=leF(a$,i-1)+mI(a$,j+1):gO1
6ifmI(a$,m,1)<>mI(a$,n,1)tH3
7m=m+1:n=n-1:gO5
8?a$

Try in emulator

Answer 6

JavaScript (Node.js), 214 bytes

f=s=>[...s,t=[]].map((_,i,a)=>[...Array(i).keys()].map(j=>j<i-2&&s.slice(j,(j+i)/2|0)==a.slice((j+i+1)/2|0,i).reverse().join``&&t.push(s.slice(0,j)+s.slice(i))))&&0 in t?t.map(f).sort((x,y)=>x.length-y.length)[0]:s

Try it online!

Explanation

• f=s=>...: Define a function f (named so recursion is possible) which solves the challenge for a string s
• [...s,t=[]].map((_,i,a)=>...): For every integer i from 0 to the length of s, do the following... (with the characters of s stored in the array a)
  • [...Array(i).keys()].map(j=>j<i-2&&...): For every integer j from 0 to i-1, where j < i-2, do the following...
    • s.slice(j,(j+i)/2|0)==a.slice((j+i+1)/2|0,i).reverse().join``: Check if the slice of s ranging from j to i is a palindrome
    • ...&&t.push(s.slice(0,j)+s.slice(i)) If so, push the section of s without the palindrome to t
• &&0 in t?...:s: Now, if t is empty, return s unchanged. Otherwise, one or more palindromes was found
• t.map(f): For each palindrome found in s, recursively apply f to the parts of s without that palindrome
• .sort((x,y)=>x.length-y.length)[0]: Choose the shortest result possible

Answer 7

Perl 5 -pl, 109 bytes

chomp;@,=$s=$_;/((.)(?1)\2|(.)(.)\4?\3)?(??{$1?push@,,$`.$':length$s>y!!!c?$s=$_:1;0})/,$_=pop@,while@,;$_=$s

Try it online!

Speed is not great. I'd claim further "-6" from the score -- chomping is only required for the "nice" TIO's many-inputs-in-the-same-screen presentation, not for an input of a single string w/o trailing LF (the same about "-l" switch.)

More readable:

chomp;
@, = $s = $_;
/
    ( (.)(?1)\2 | (.)(.)\4?\3 )?
    (??{ 
        $1 ? push @,, $` . $'
           : length $s > y!!!c ? $s = $_ : 1;
        0
    })
/x,
$_ = pop @, while @,;
$_ = $s

Answer 8

Charcoal, 47 bytes

?υＳＦυＦＬιＦＥι?ικμＦ∧?Ｌλ2?λ?λ?υΦι÷?ξκＬλ§υ?ＥυＬι?ＥυＬι

Try it online! Link is to verbose version of code. Explanation:

?υＳＦυ

Start searching for palindromic substrings starting with the input.

ＦＬιＦＥι?ικμＦ∧?Ｌλ2?λ?λ

If this substring is long enough and palindromic, then...

?υΦι÷?ξκＬλ

... filter it out from the string and push the result to the list of strings to test.

§υ?ＥυＬι?ＥυＬι

Output the shortest resulting string.

Answer 9

Python, 146 145 140 bytes

def f(s):
 L=len(s);w=[s]
 for a in range(L):
  for b in range(a+3,L+1):s[a:b]==s[a:b][::-1]==(w:=w+[f(s[:a]+s[b:])])
 return min(w,key=len)

Attempt This Online!