24
\$\begingroup\$

The shortest code that finds all unique "sub-palindromes" of a string, that is: any substring with length > 1 that is a palindrome.

eg.1

input: "12131331"
output: "33", "121", "131", "313", "1331"

eg.2

input: "3333"
output: "33", "333", "3333"
\$\endgroup\$
  • 1
    \$\begingroup\$ Can a string be it's own sub-palindrome? Since a string is it's own substring. \$\endgroup\$ – JPvdMerwe Jan 29 '11 at 12:17
  • \$\begingroup\$ @JPvdMerwe: Yes, off course. \$\endgroup\$ – Eelvex Jan 29 '11 at 12:39
  • \$\begingroup\$ Actually more importantly: what must the output of 333 be? Naively you'd end up printing 33 twice \$\endgroup\$ – JPvdMerwe Jan 29 '11 at 12:41
  • \$\begingroup\$ @JPvdMerwe: '333' -> '33', '333'. I'll edit the question accordingly. Thanks. \$\endgroup\$ – Eelvex Jan 29 '11 at 12:53
  • \$\begingroup\$ How is the output specified? Comma-delimited with quotes areound each sub-palindrome as you demonstrate here? One sub-p per line? \$\endgroup\$ – Joey Jan 30 '11 at 12:58

31 Answers 31

11
\$\begingroup\$

J, 24 31 40

~.(#~(1<#*]-:|.)&>),<\\.

Sample use:

   ~.(#~(1<#*]-:|.)&>),<\\. '12131331'
┌───┬───┬───┬────┬──┐
│121│131│313│1331│33│
└───┴───┴───┴────┴──┘
   ~.(#~(1<#*]-:|.)&>),<\\. '3333'
┌──┬───┬────┐
│33│333│3333│
└──┴───┴────┘

Take that, GolfScript!

\$\endgroup\$
  • \$\begingroup\$ Admit it, you just put a dump from /dev/random here to fool us ;-) \$\endgroup\$ – Joey Feb 12 '11 at 18:17
  • \$\begingroup\$ @Joey try it for yourself ;p (TBH, I didn't believe it could work either at first) \$\endgroup\$ – J B Feb 12 '11 at 18:22
  • \$\begingroup\$ I'm fairly sure it's actual code. I spent a weekend trying to wrap my head around J, but failed miserably. Still, I recognize code; I just don't understand what it does ;-) \$\endgroup\$ – Joey Feb 12 '11 at 19:12
  • 2
    \$\begingroup\$ Can't this be shortened to ~.(#~(1<#*]-:|.)&>),<\\. (24 characters)? \$\endgroup\$ – ephemient Apr 4 '12 at 20:24
  • \$\begingroup\$ @ephemient It does indeed. (Looks like I was stuck in the "answer must be a function" mindset, which does not apply here.) Edited, thanks! \$\endgroup\$ – J B Apr 12 '12 at 12:26
7
\$\begingroup\$

Python 124

r=raw_input()
l=range(len(r))
print', '.join(set('"'+r[i:j+1]+'"'for i in l for j in l if i<j and r[i:j+1]==r[i:j+1][::-1]))
\$\endgroup\$
5
\$\begingroup\$

Haskell 98, 88 91 96

import List
main=interact$show.filter(\x->length x>1&&x==reverse x).nub.(tails=<<).inits
\$\endgroup\$
3
\$\begingroup\$

Python - 138 136

This code does not duplicate sub-palindromes.

r=raw_input()
i,l=0,len(r)
j=l
a=[]
while i<l-1:
 t=r[i:j];j-=1
 if t==t[::-1]:a+=['"'+t+'"']
 if j<i+2:i+=1;j=l
print", ".join(set(a))
\$\endgroup\$
  • 1
    \$\begingroup\$ Change '"'+t+'"' to t to save some space, although it uses single quotes. \$\endgroup\$ – Thomas O Jan 30 '11 at 12:00
3
\$\begingroup\$

Ruby - 126 102 97 characters

s=gets
*m=*0..s.size
puts m.product(m).map{|h,j|(c=s[h,j+1]).size>1&&c==c.reverse ? c:0}.uniq-[0]
\$\endgroup\$
3
\$\begingroup\$

Golfscript, 48 characters

subpalindrome.gs

{,}{(;}/{{,}{);}/}%{+}*{.,1>\.-1%=*},.&{`}%", "*

Usage:

echo "12131331" | ruby golfscript.rb subpalindrome.gs

The first operation {,}{(;}/ turns a string into a list of trailing-substrings. A similar leading-substrings transform is then mapped over the result. Then flatten with {+}*, filter for palindromes using the predicate .,1>\.-1%=*, grab unique values with .&, then pretty print.

It would be neater to extract the trailing-substrings transform as a block and reuse it as a replacement for leading-substrings after reversing each trailing substring, but I can't figure out a succinct way of doing that.

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

Haskell - 170, 153

import Data.List
import Data.Set
p a=fromList$[show x|x<-subsequences a,x==reverse x,length x>1]
main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x)
\$\endgroup\$
  • \$\begingroup\$ Replace main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x) with main=getLine>>=putStrLn.intercalate", ".toList.p. I would also substitute a call to p with its body. \$\endgroup\$ – Yasir Arsanukaev Feb 1 '11 at 15:37
  • \$\begingroup\$ Substrings /= subsequences! Your program reports more subpalindromes than the reference output for example 1. ("1111" for instance) \$\endgroup\$ – J B Feb 10 '11 at 23:13
2
\$\begingroup\$

J, 48

f=:,@:".
h=:\\.
~.(#~10&<)((]h-:"0&f|.h)#[:f]h)

eg

~.(#~10&<)((]h-:"0&f|.h)#[:f]h) '12131331'
121 131 313 1331 33
\$\endgroup\$
2
\$\begingroup\$

Prolog, 92

f(S,P):-append([_,X,_],S),X=[_,_|_],reverse(X,X),atom_codes(P,X).
p(S,R):-setof(P,f(S,P),R).

Sample use:

?- p("12131331",R).
R = ['121', '131', '1331', '313', '33'].

?- p("3333",R).
R = ['33', '333', '3333'].
\$\endgroup\$
2
\$\begingroup\$

Windows PowerShell, 104 109 111

0..($l=($s="$input").length-1)|%{($a=$_)..$l|%{-join$s[$a..$_]}}|sort -u|?{$_[1]-and$_-eq-join$_[$l..0]}

This expects the input on stdin and will throw all found palindromes one per line on stdout:

PS Home:\SVN\Joey\Public\SO\CG183> '12131331'| .\subp.ps1
33
121
131
313
1331

(When run from cmd it becomes echo 12131331|powershell -file subp.ps1 – it's just that $input takes a slightly different meaning depending on how the script was called, but it can be stdin, just not interactively.)

2011-01-30 13:57 (111) – First attempt.

2011-01-30 13:59 (109) – Inlined variable declaration.

2011-06-02 13:18 (104) – Redone substring finding by joining a char array instead of calling .Substring() and inlined a bit more.

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

Q, 78

{a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}

usage

q){a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}"12131331"
"121"
"131"
"313"
"1331"
"33"
q){a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}"3333"
"33"
"333"
"3333"
\$\endgroup\$
2
\$\begingroup\$

Retina, 34 27 bytes

&@!`(.)+.?(?<-1>\1)+(?(1)^)

Try it online!

The test suite needs an M because it is followed by another stage to insert empty lines between test cases.

Explanation

&@!`(.)+.?(?<-1>\1)+(?(1)^)

Print (!) all unique (@), overlapping (&) matches of the regex (.)+.?(?<-1>\1)+(?(1)^). This matches a palindrome of length 2 or more using balancing groups. There's a caveat to the "all overlapping matches" part: we can get at most one match per starting position. However, if two palindromes of different length begin at the same position, the shorter palindrome will appear again at the end of the longer palindrome. And since the greediness of + prioritises longer matches, we're getting all palindromes anyway.

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

05AB1E, 11 10 bytes

ŒÙʒÂQ}žQSK

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 9 bytes \$\endgroup\$ – scottinet Oct 25 '17 at 21:30
  • \$\begingroup\$ @scottinet fails for singles, E.G.1234142141410010101000 \$\endgroup\$ – Magic Octopus Urn Oct 25 '17 at 21:38
  • 1
    \$\begingroup\$ Yours too, but not in the same way. o_O There is something going on that needs investigation. In the meantime, here is a 10 bytes version that seems to work \$\endgroup\$ – scottinet Oct 25 '17 at 21:43
  • \$\begingroup\$ There was a bug with uniquify, I fixed it. Now both your 11 bytes answer and my 9 bytes one work :-) \$\endgroup\$ – scottinet Oct 27 '17 at 21:55
  • \$\begingroup\$ @scottinet Your 10-byter can be a 9-byter as well by changing 1› to . :) \$\endgroup\$ – Kevin Cruijssen Feb 7 at 13:11
1
\$\begingroup\$

Perl, 112

$_=<>;chop;s/./$&$' /g;
map{/../&&$_ eq reverse&&$h{$_}++}split/ /
  for grep{s/./$`$& /g}split/ /;
print for keys %h
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 120 bytes

a=>{for(b=0,c=d=a.length,e=[];b<d;--c<b+2?(b++,c=d):1)(f=a.slice(b,c))==f.split``.reverse().join``&&e.push(f);return e}

This function takes a string as input and outputs an array.

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

Clojure, 81 bytes

#(set(for[i(range 2(+(count %)1))p(partition i 1 %):when(=(reverse p)(seq p))]p))

for was a perfect match here :) Could use :when(=(reverse p)p) if input was a list of characters OR a full string didn't count as a palindrome, actually in that case the max range of i could be (count %) as well.

Most compact case for reference:

#(set(for[i(range 2(count %))p(partition i 1 %):when(=(reverse p)p)]p))
\$\endgroup\$
1
\$\begingroup\$

Python, 83 102 chars

s=lambda t:(t[1:]or())and(t,)*(t==t[::-1])+s(t[1:])+s(t[:-1])
print set(s(input()))

The phrase (t[1:]or())and... is equivalent to (...)if t[1:]else() and saves one character! I'm overly proud of this, given the savings.

Example:

python x
"51112232211161"
set(['11', '22', '11122322111', '161', '111', '112232211', '1223221', '22322', '232'])
\$\endgroup\$
1
\$\begingroup\$

Scala 127

object p extends App{val s=args(0);print(2.to(s.size).flatMap(s.sliding(_).toSeq.filter(c=>c==c.reverse)).toSet.mkString(" "))}

To keep this an apples to apples comparison with the other Scala answer, I also made mine an object that extends App. Rather than iterate the input string manually and use substring, I leveraged sliding() to create a sequence of all the substrings for me.

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

Scala 156 170

object o extends App{val l=args(0).length-2;val r=for(i<-0 to l;j<-i to l;c=args(0).substring(i,j+2);if(c==c.reverse))yield c;print(r.toSet.mkString(" "))}

object o{def main(s:Array[String]){val l=s(0).length-2;val r=for(i<-0 to l;j<-i to l;c=s(0).substring(i,j+2);if(c==c.reverse)) yield c;println(r.distinct.mkString(" "))}}

\$\endgroup\$
  • \$\begingroup\$ Hi Lalith, I shortened your code a bit: No blank before yield and extending App instead of overwriting main, println => print and distinct=>toSet \$\endgroup\$ – user unknown Apr 4 '12 at 14:14
1
\$\begingroup\$

Perl 6,  35  32 bytes

{unique ~«m:ex/(.+).?<{$0.flip}>/}

Test it

{set ~«m:ex/(.+).?<{$0.flip}>/}

Test it

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  set             # turn into a Set object (ignores duplicates)

  ~«\             # stringify 「~」 all of these 「«」 (possibly in parrallel)
                  # otherwise it would be a sequence of Match objects

  m               # match
  :exhaustive     # in every way possible
  /
    ( .+ )        # at least one character 「$0」
    .?            # possibly another character (for odd sized sub-palindromes)
    <{ $0.flip }> # match the reverse of the first grouping
  /
}
\$\endgroup\$
1
\$\begingroup\$

Coconut, 69 bytes

def f(s)=s and{s*(s[::-1]==s>""<s[1:])}-{""}|f(s[1:])|f(s[:-1])or s{}

Try it online!


Python 2, 73 bytes

f=lambda s:s and{s*(s[::-1]==s>""<s[1:])}-{""}|f(s[1:])|f(s[:-1])or set()

Try it online!

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

Jelly, 9 bytes

ẆQŒḂÐfḊÐf

Try it online!

\$\endgroup\$
  • \$\begingroup\$ The output of your permalink is incorrect. \$\endgroup\$ – Dennis Feb 13 '18 at 16:30
  • \$\begingroup\$ @Dennis why did this become a dupe target then >_> fixed \$\endgroup\$ – Erik the Outgolfer Feb 13 '18 at 17:43
  • \$\begingroup\$ 7 bytes with new Jelly. \$\endgroup\$ – user202729 May 24 '18 at 14:37
1
+100
\$\begingroup\$

APL (Dyalog Classic), 27 bytes

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/1↓⍳∘≢,/¨⊂)

Try it online!

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/1↓⍳∘≢,/¨⊂)    Monadic train:
                           ⊂     Enclose the input, ⊂'12131331'
                     ⍳∘≢          Range from 1 to length of input
                     ⍳∘≢,/¨⊂      List of list of substrings of each length
                   1↓            Remove the first list (length-1 substrings)
               ⊃ ,/              Put the rest of the substrings into a single list.
{∪⍵/⍨≡∘⌽¨⍨⍵}                   To the result, apply this function which
                                   keeps all palindromes from a list:
      ≡∘⌽¨⍨⍵                    Boolean value of whether each (¨) string in argument
      ≡∘⌽ ⍨                     is equal to its own reverse

  ⍵/⍨                           Replicate (filter) argument by those values.
                                 This yields the length >1 palindromes.
∪                                Remove duplicates from the list of palindromes.
\$\endgroup\$
  • \$\begingroup\$ Due to OP calling for "code", the snippet ∪w/⍨≡∘⌽¨⍨w←⊃,/1↓(⍳∘≢,/¨⊂) is valid. \$\endgroup\$ – Adám Feb 7 at 9:11
  • \$\begingroup\$ @Adám I think I'll keep this answer as it is for the sake of modern site standards, especially since it doesn't get the overall win. \$\endgroup\$ – lirtosiast Feb 7 at 19:08
1
\$\begingroup\$

Japt, 14 bytes

Êò2@ãX fêSÃc â

Try it online!

Explanation:

Êò2               #Get the range [2...length(input)]
   @      Ã       #For each number in that range:
    ãX            # Get the substrings of the input with that length
       fêS        # Keep only the palindromes
           c      #Flatten
             â    #Keep unique results
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 99 bytes

$args|% t*y|%{$s+=$_
0..$n|%{if($n-$_-and($t=-join$s[$_..$n])-eq-join$s[$n..$_]){$t}}
$n++}|sort -u

Try it online!

Less golfed:

$args|% toCharArray|%{
    $substring+=$_
    0..$n|%{
        if( $n-$_ -and ($temp=-join$substring[$_..$n]) -eq -join$substring[$n..$_] ){
            $temp
        }
    }
    $n++
}|sort -Unique
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 11 bytes

{s.l>1∧.↔}ᵘ

Try it online!

(The header in the link is broken at the time of posting, so here's the predicate (function-equivalent in Brachylog) on only the first test case, with a w at the end to actually print the output.)

               The output is
{        }ᵘ    a list containing every possible unique
 s.            substring of
               the input
   l           the length of which
    >          is greater than
     1         one
      ∧        and
       .       which
        ↔      reversed
               is itself. (implicit output within the inline sub-predicate)

I feel like there's a shorter way to check that the length is greater than 1. (If it didn't filter out trivial palindromes, it would just be {s.↔}ᵘ.)

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

APL(NARS), 65 chars, 130 bytes

{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}

test:

  r←{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}
  o←⎕fmt
  o r '1234442'
┌2───────────┐
│┌2──┐ ┌3───┐│
││ 44│ │ 444││
│└───┘ └────┘2
└∊───────────┘
  o r '3333'
┌3───────────────────┐
│┌4────┐ ┌3───┐ ┌2──┐│
││ 3333│ │ 333│ │ 33││
│└─────┘ └────┘ └───┘2
└∊───────────────────┘
  o r  "12131331"
┌5─────────────────────────────────┐
│┌4────┐ ┌3───┐ ┌2──┐ ┌3───┐ ┌3───┐│
││ 1331│ │ 121│ │ 33│ │ 313│ │ 131││
│└─────┘ └────┘ └───┘ └────┘ └────┘2
└∊─────────────────────────────────┘
  o r '1234'
┌0─┐
│ 0│
└~─┘


{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}
 y←⍵  assign the argument to y (because it has to be used inside other function)
 x←11 1‼k k⊢k←≢y   assign the lenght of y to k, call the function 11 1‼k k
                   that seems here find all partition of 1 2 ..k
 {x[⍵;]⊂y}¨⍳≢      make partition of arg ⍵ using that set x
 ∪/                set union with precedent to each element of partition y (i don't know if this is ok)
 b←↑               get first assign to b
 {1≥≢⍵:0⋄∧/⍵=⌽⍵}¨ for each element of b return 1 only if the argument ⍵ is such that 
                   "∧/⍵=⌽⍵" ⍵ has all subset palindrome, else return 0
 b/⍨               get the elements in b for with {1≥≢⍵:0⋄∧/⍵=⌽⍵} return 1
 m←∪               make the set return without ripetition element, and assign to m
 0=≢               if lenght of m is 0 (void set) than 
 :⍬⋄m              return ⍬ else return m

it someone know better why, and can explain this better, free of change this all... I am not so certain of this code, possible if test examples are more numerous, something will go wrong...

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

Japt, 9 bytes

ã â fÅfêU

Try it

ã â fÅfêU     :Implicit input of string
ã             :Substrings
  â           :Deduplicate
    f         :Filter elements that return truthy
     Å        :  Slice off first character
       f      :Filter elements that return true
        êU    :  Test for palindrome
\$\endgroup\$
0
\$\begingroup\$

Java 8, 202 201 199 bytes

import java.util.*;s->{Set r=new HashSet();String x;for(int l=s.length(),i=0,j;i<l;i++)for(j=i;++j<=l;)if((x=s.substring(i,j)).contains(new StringBuffer(x).reverse())&x.length()>1)r.add(x);return r;}

Try it here.

If a function isn't allowed and a full program is required, it's 256 255 253 bytes instead:

import java.util.*;interface M{static void main(String[]a){Set r=new HashSet();String x;for(int l=a[0].length(),i=0,j;i<l;i++)for(j=i;++j<=l;)if((x=a[0].substring(i,j)).contains(new StringBuffer(x).reverse())&x.length()>1)r.add(x);System.out.print(r);}}

Try it here.

Explanation:

import java.util.*;      // Required import for Set and HashSet

s->{                     // Method with String parameter and Set return-type
  Set r=new HashSet();   //  Return-Set
  String t;              //  Temp-String
  for(int l=s.length(),  //  Length of the input-String
          i=0,j;         //  Index-integers (start `i` at 0)
      i<l;i++)           //  Loop (1) from `0` to `l` (exclusive)
    for(j=i;++j<=l;)     //   Inner loop (2) from `i+1` to `l` (inclusive)
      if((t=s.substring(i,j) 
                         //    Set `t` to the substring from `i` to `j` (exclusive)
         ).contains(new StringBuffer(t).reverse())
                         //    If this substring is a palindrome,
         &t.length()>1)  //    and it's length is larger than 1:
        r.add(t);        //     Add the String to the Set
                         //   End of inner loop (2) (implicit / single-line body)
                         //  End of loop (1) (implicit / single-line body)
  return r;              //  Return the result-Set
}                        // End of method
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 107 bytes

Returns a Set.

s=>new Set((g=(s,r=[...s].reverse().join``)=>s[1]?(r==s?[s]:[]).concat(g(s.slice(1)),g(r.slice(1))):[])(s))

Test cases

let f =

s=>new Set((g=(s,r=[...s].reverse().join``)=>s[1]?(r==s?[s]:[]).concat(g(s.slice(1)),g(r.slice(1))):[])(s))

console.log([...f('12131331').values()])
console.log([...f('3333').values()])

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