28
\$\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\$
7
  • 1
    \$\begingroup\$ Can a string be it's own sub-palindrome? Since a string is it's own substring. \$\endgroup\$
    – JPvdMerwe
    Jan 29, 2011 at 12:17
  • 1
    \$\begingroup\$ @JPvdMerwe: Yes, off course. \$\endgroup\$
    – Eelvex
    Jan 29, 2011 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, 2011 at 12:41
  • \$\begingroup\$ @JPvdMerwe: '333' -> '33', '333'. I'll edit the question accordingly. Thanks. \$\endgroup\$
    – Eelvex
    Jan 29, 2011 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, 2011 at 12:58

37 Answers 37

1
2
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\$

Stax, 10 bytes

îmmW┴√▄○○←

Run and debug it

I couldn't find an is-palindrome function. With that this'd probably be much shorter.

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

Husk, 11 9 8 bytes

Edit: -1 byte thanks to Razetime

uftfS=↔Q

Try it online!

uftfS=↔Q
u               # unique elements of
       Q        # all contiguous subsets of input
 f              # after filtering to include only those that
  t             # are not a single digit/character
   f            # and then filtering to include only those that
    S=↔         # are equal to themselves reversed
\$\endgroup\$
4
  • \$\begingroup\$ when in doubt, filter twice \$\endgroup\$
    – Razetime
    Nov 16, 2020 at 8:50
  • \$\begingroup\$ 8 bytes \$\endgroup\$
    – Razetime
    Nov 16, 2020 at 8:52
  • \$\begingroup\$ Thanks! I think I maybe need a look-up table to indicate when combinators actually save bytes, and when they're just a complicated liability... \$\endgroup\$ Nov 16, 2020 at 9:07
  • \$\begingroup\$ § generally isn't worth it in a full program(Or inside brackets). Removing them makes type inference happy, \$\endgroup\$
    – Razetime
    Nov 16, 2020 at 9:09
1
\$\begingroup\$

Thunno 2, 7 bytes

FœḣæḲ:U

Try it online!

Explanation

FœḣæḲ:U  # Implicit input
F        # All substrings of the input
 œḣ      # Filter by length > 1
   æḲ:   # Only keep palindromes
      U  # Uniquify this list
         # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Nekomata, 8 bytes

qNᵗz:↔=ũ

Attempt This Online!

qNᵗz:↔=ũ
q           Find a contiguous subsequence of the input
 N          Check that it is nonempty
  ᵗz        Check that it is not a singleton
    :       Duplicate
     ↔      Reverse
      =     Check equality
       ũ    Remove duplicate results
\$\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\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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