# 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 '11 at 23:29
• @J B: may be omitted. Where is the mismatch? – Eelvex Feb 11 '11 at 23:34
• @Eelvex "subsequences that are not substrings". That part reads like substrings aren't allowed. – J B Feb 11 '11 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. – Eelvex Feb 12 '11 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 '11 at 11:12

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



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 :) – Eelvex Feb 12 '11 at 10:47