Having spend some time on this site I have come to enjoy things being as short as possible. That may be the reason why I'm recently kind of offended by strings containing the same characters more than once. Your job is to write a function or program which condenses a given string according to the following rules:

  • Start with a 0-condensation, that is look for the first (leftmost) pair of the same characters with 0 other characters between them. If such a pair is found, remove one of the two characters and restart the algorithm by performing another 0-condensation. If no such pair is found, proceed with the next step. Examples:
    programming -C0-> programing
    aabbcc -C0-> abbcc
    test -C0-> test

  • Then perform a 1-condensation, that is look for the first pair of same characters with 1 other character between them. If such a pair is found remove one of them and all characters between them and restart with a 0-condensation. If no such pair is found, proceed with the next step. Examples:
    abacac -C1-> acac
    java -C1-> ja

  • Continue with a 2-condensation and so on up to a n-condensation with n being the length of the original string, each time restarting after a condensation removed some letters. Examples:
    programing -C2-> praming
    abcdafg -C3-> afg

The resulting string is called condensed and contains each character at most once.


A lower case string of printable ascii-characters.


The condensed string according to the rules above.


examples     -> es
programming  -> praming
puzzles      -> puzles
codegolf     -> colf
andromeda    -> a
abcbaccbabcb -> acb
if(x==1):x++ -> if(x+
fnabnfun     -> fun
abcdefae     -> abcde

Detailed examples to clarify how the algorithm works:

fnabnfun -C0-> fnabnfun -C1-> fnabnfun -C2-> fnfun -C0-> fnfun -C1-> fun -C0-> fun 
 -C1-> fun -C2-> ... -C8-> fun

abcbaccbabcb -C0-> abcbacbabcb -C0-> abcbacbabcb -C1-> abacbabcb -C0-> abacbabcb 
 -C1-> acbabcb -C0-> acbabcb -C1-> acbcb -C0-> acbcb -C1-> acb -C0-> acb 
 -C1-> ... -C12-> acb

Your approach doesn't have to implement the algorithm from above as long as your solution and the algorithm return the same output for all allowed inputs. This is a challenge.

Thanks to @Linus for helpful sandbox comments!

  • \$\begingroup\$ @MartinEnder Riley's test case is still necessary, because it's the only one my Retina solution doesn't work on. \$\endgroup\$
    – mbomb007
    Sep 27, 2016 at 13:27
  • \$\begingroup\$ @mbomb007 Ah, I see. Good point. \$\endgroup\$ Sep 27, 2016 at 13:40
  • \$\begingroup\$ Will the input string ever contain non-printable characters like spaces? \$\endgroup\$
    – mbomb007
    Sep 27, 2016 at 13:58
  • \$\begingroup\$ @mbomb007 No, to assume printable ascii characters only is fine. \$\endgroup\$
    – Laikoni
    Sep 27, 2016 at 14:30
  • \$\begingroup\$ @mbomb007 However as far as I know, a space is considered a printable ascii character, e.g. here. \$\endgroup\$
    – Laikoni
    Sep 27, 2016 at 15:22

9 Answers 9


JavaScript (ES6), 74 bytes

<input oninput=o.textContent=f(this.value)><pre id=o>

  • \$\begingroup\$ Very nice, shorter than what I would have thought of. \$\endgroup\$ Sep 26, 2016 at 23:04

Perl, 38 31 30 29 bytes

This should should leave the non-golfing languages far behind...

-1 for $-[0] thanks to Riley

-1 for @{-} thanks to Dada

Includes +1 for -p

Give input on STDIN


#!/usr/bin/perl -p
s/(.)\K.{@{-}}\1// while/./g

This 27 byte version should work but it doesn't because perl doesn't interpolate @- in a regex (see https://stackoverflow.com/questions/39521060/why-are-etc-not-interpolated-in-strings)

#!/usr/bin/perl -p
s/(.)\K.{@-}\1// while/./g
  • \$\begingroup\$ How does the @{\@-} part work? I thought @- held the indexes of each match, so how does it "count up" on every iteration. Also, if you print @{\@-} before and after each substitution it only ever prints 1 or 2. \$\endgroup\$
    – Riley
    Sep 27, 2016 at 13:57
  • 1
    \$\begingroup\$ @Riley The /./g progresses by 1 in the string each time, except when the string changes, then it's reset to 0. If you print @- after the /./g but before the s/// you will see it going up (use a test where the remaining string is large enough) \$\endgroup\$
    – Ton Hospel
    Sep 27, 2016 at 14:13
  • \$\begingroup\$ Printing $-[0] gives the numbers I would expect. Does @{\@-} act like $-[0] because of the regex context but not when printing for some reason? $-[0] is a byte shorter than @{\@-} if they are the same. \$\endgroup\$
    – Riley
    Sep 27, 2016 at 14:22
  • \$\begingroup\$ "@{\@-}" is not the same as @{\@-} (without "). \$\endgroup\$
    – Riley
    Sep 27, 2016 at 14:38
  • \$\begingroup\$ @Riley No, but "@{\@-}" is the same as "@-". And this should also be true for a regex substitution but it isn't. Simularly $-[0] should work but doesn't. PS: You probably somehow had scalar context applied to @- when you did your print, so you always got 1 or 2 \$\endgroup\$
    – Ton Hospel
    Sep 27, 2016 at 15:58

CJam, 35 bytes


Try it online!

rL{                            }j   | run recursion on input
   _,{                      }fI     | for I from 0 to length(input)
      {                 }h]s        | one pass & clean up
       (_@                          | slice and store leading element A
          _@#I={      }*            | if next A is I steps away
                I)>                 | slice off I+1 element
                   ]sj              | clean up & recursion

You can see the individual condensations by inserting ed


Python 2, 117 104 101 bytes

Recursively do the necessary replacements. I build the regex dynamically.

import re
def f(s,i=0):t=re.sub(r"(.)%s\1"%("."*i),r"\1",s);e=s==t;return i>len(t)and t or f(t,i*e+e)

Try it online

  • \$\begingroup\$ The two return lines can be condensed into return i>len(t) and t or s!=t and f(t) or f(t,i+1) for a net of -4 bytes \$\endgroup\$
    – Quelklef
    Sep 26, 2016 at 23:47
  • \$\begingroup\$ Another 2 bytes can be shaved off by changing that to return t if i>len(t)else s!=t and f(t)or f(t,i+1)) \$\endgroup\$
    – Quelklef
    Sep 26, 2016 at 23:51
  • \$\begingroup\$ Even more by e=s==t;return i>len(t)and t or f(t,i*e+e) and then you can remove the i=0 in the function definition, but you'll have to call with 0 start. \$\endgroup\$
    – Quelklef
    Sep 26, 2016 at 23:59
  • \$\begingroup\$ I'm going to assume that the four spaces are there not because you're using four spaces but because SE automatically expands them. If that's not the case, you can change all your spaces to either tabs or a single space for -9 bytes. \$\endgroup\$
    – anon
    Sep 27, 2016 at 3:32
  • \$\begingroup\$ @Quelklef The meta forbids taking additional parameters. \$\endgroup\$
    – mbomb007
    Sep 27, 2016 at 13:21

Perl 53 52

Includes +1 for -p


Try it on ideone.


Mathematica, 101 bytes


There should be a way to make this shorter...


PHP, 90 Bytes


or 92 Bytes

  • 1
    \$\begingroup\$ 1) first version: +$i instead of $i+=0 (-2). 2) for loop instead of while can save two bytes and allow to remove curlys (-4). 3) $i=++$i*!$c instead of $i=$c?0:$i+1 (-1). 4) \\2 is not needed, remove parentheses (-2). 5) You can allow limit 9 instead of 1 for speed (+0) \$\endgroup\$
    – Titus
    Sep 29, 2016 at 13:06
  • \$\begingroup\$ @Titus very good ideas. I had't see this Thank You \$\endgroup\$ Sep 29, 2016 at 13:58
  • \$\begingroup\$ Now that I think again ... +$i doesn´t work in every case. Try hammer. PHP doesn´t complain about the empty braces in the regex; but it doesn´t match as wanted. By the way: I count 91, not 90. But try the new 1) for($s=$argv[$c=1];$s[$i=++$i*!$c];) \$\endgroup\$
    – Titus
    Sep 29, 2016 at 17:39
  • \$\begingroup\$ @Titus Yes indeed I go back to $i+=0 and will try your proposal later. What do mean with hammer? \$\endgroup\$ Sep 29, 2016 at 18:18
  • \$\begingroup\$ @Titus okay the same problem if puzzle or something else like (.)//1 but it is okay with your proposal or the $i´=0 \$\endgroup\$ Sep 29, 2016 at 22:12

Ruby, 75 64 57 bytes

(56 bytes of code + p command line option.)

Using string interpolation inside a regex to control the length of the matches that are replaced.

~/(.).{#{i}}\1/?sub($&,$1)&&i=0: i+=1while i<$_.size


$ ruby -p condense.rb <<< fnabnfun

Haskell, 97 88 bytes

m?s|length s<m=s|a<-s!drop m s=sum[m+1|a==s]?a

Try it online!

Old 97 byte bersion:

m?s|length s==m=s|a<-s!drop m s=(last$0:[m+1|a==s])?a

Try it on ideone.


(a:s)!(b:t)|a==b = a:t         --perform condensation
           |1<3  = a:s!t       --recursively compare further
 s   ! _         = s           --no condensation performed

The (!) function performs one n-condensation when given a string once whole and once with the first n characters removed, e.g. abcdbe and cdbe for a 2-condensation, by recursively comparing the two leading characters.

m?s|length s==m   = s         --stop before performing length-s-condensation
   |a <- s!drop m s           --a is the m-condensation of s
    = (last$0:[m+1|a==s])?a   --disguised conditional:
                              -- if a==s       if the m-condensation did not change s
                              -- then (m+1)?a  then perform m+1-condensation
                              -- else 0?a      else restart with a 0-condensation

c=(0?)                        -- main function, initialise m with 0

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.