# Finding "sub-palindromes" 2: subsequences.

The same task as Finding "sub-palindromes" but instead of finding substrings you must find subsequences that are not substrings.

eg1:

input: "12131331"
output:
"11", "33", "111", "121", "131", "313", "333", "1111", "1331", "11311", "13331"
or
"11", "33", "111", "333", "1111", "11311", "13331"

eg2:

input: "3333"
output:
"33", "333"
or
(null)
• Input is a string of printable ascii characters.
• Output is a list of unique strings.
• If a subsequence also appears as a substring it may be omitted.
• Shortest code wins.
• It may be omitted or it must be omitted? Header and details don't match.
– J B
Feb 11, 2011 at 23:29
• @J B: may be omitted. Where is the mismatch? Feb 11, 2011 at 23:34
• @Eelvex "subsequences that are not substrings". That part reads like substrings aren't allowed.
– J B
Feb 11, 2011 at 23:53
• @J-B: Substrings are not allowed. What you may or may not omit is a subsequence that also appears as a substring. Take a look at the examples: "1331" is a subsequence "12 13 13 31 " but also a substring "1213 1331 " so you may omit it. Feb 12, 2011 at 0:09
• @Eelvex: look at it this way. The example output includes "1331". But "1331" is a substring. Thus I don't understand why it's there, given that substrings are not allowed.
– J B
Feb 12, 2011 at 11:12

import Data.List
main=interact f
f a=show.nub.filter(\x->(not$isInfixOf a x)&&x==reverse x&&length x>1)$subsequences a

Isn't too difficult with a builtin subsequences and nub... :)

## Golfscript (95)

);.{{(\a\:x;.{[x]\+}%+}:b;{.!{[$]}{b}if}:a;.a{..-1%=&},\{,}{(;}/{{,}{);}/}%{+}*-.&{}%", "*}and I haven't really tried to golf this further, it's just a combination of left overs. The question is inconsistent. My program prints all palindromic subsequences that are not substrings. Hope this is OK. Example 1: echo "12131331" | ruby golfscript.rb subseq_not_substr.gs "11", "111", "13331", "13131", "1111", "11311" Example 2: echo "3333" | ruby golfscript.rb subseq_not_substr.gs Empty String Example: echo "" | ruby golfscript.rb subseq_not_substr.gs With uglier output formatting, eg [11 111 13331 13131 1111 11311], it could be made a bit shorter. • Any way of formatting the output list is ok. Make it shorter :) Feb 12, 2011 at 10:47 ### GolfScript, 39 characters :^1/[""]\{{1$\+}+%}/.&{..-1%=^@?0<&},

Examples:

> "12131331"
["11" "333" "111" "13331" "13131" "1111" "11311"]

> "3333"
[]

Basic blocks of the code:

# Save input in variable
:^

# Build all possible subsequences of the input
1/[""]\{{1\$\+}+%}/

# Filter unique ones
.&

# Filter relevant palindromes
{.
.-1%=   # check if palindrome
^@?0<   # check if sequence is no substring
&       # and operation on both
},

# Format output
`