Code Golf: Duplicate Character Removal in String

Viewed 5215

The challenge: The shortest code, by character count, that detects and removes duplicate characters in a String. Removal includes ALL instances of the duplicated character (so if you find 3 n's, all three have to go), and original character order needs to be preserved.

Example Input 1:
nbHHkRvrXbvkn

Example Output 1:
RrX


Example Input 2:
nbHHkRbvnrXbvkn

Example Output 2:
RrX

(the second example removes letters that occur three times; some solutions have failed to account for this)

(This is based on my other question where I needed the fastest way to do this in C#, but I think it makes good Code Golf across languages.)

48 Answers

J (16 12 characters)

(~.{~[:I.1=#/.~)

Example:

(~.{~[:I.1=#/.~) 'nbHHkRvrXbvkn'
    RrX

It only needs the parenthesis to be executed tacitly. If put in a verb, the actual code itself would be 14 characters.

There certainly are smarter ways to do this.

EDIT: The smarter way in question:

(~.#~1=#/.~) 'nbHHkRvrXbvkn'
    RrX

12 characters, only 10 if set in a verb. I still hate the fact that it's going through the list twice, once to count (#/.) and another to return uniques (nub or ~.), but even nubcount, a standard verb in the 'misc' library does it twice.

C: 83 89 93 99 101 characters

  • O(n2) time.
  • Limited to 999 characters.
  • Only works in 32-bit mode (due to not #include-ing <stdio.h> (costs 18 chars) making the return type of gets being interpreted as an int and chopping off half of the address bits).
  • Shows a friendly "warning: this program uses gets(), which is unsafe." on Macs.

.

main(){char s[999],*c=gets(s);for(;*c;c++)strchr(s,*c)-strrchr(s,*c)||putchar(*c);}

(and this similar 82-chars version takes input via the command line:

main(char*c,char**S){for(c=*++S;*c;c++)strchr(*S,*c)-strrchr(*S,*c)||putchar(*c);}

)

Golfscript(sym) - 15

  .`{\{=}+,,(!}+,
+-------------------------------------------------------------------------+
||    |    |    |    |    |    |    |    |    |    |    |    |    |    |  |
|0         10        20        30        40        50        60        70 |
|                                                                         |
+-------------------------------------------------------------------------+

Javascript 1.6

s.match(/(.)(?=.*\1)/g).map(function(m){s=s.replace(RegExp(m,'g'),'')})

Shorter than the previously posted Javascript 1.8 solution (71 chars vs 85)

Assembler

Tested with WinXP DOS box (cmd.exe):

    xchg cx,bp
    std
    mov al,2
    rep stosb
    inc cl
l0: ; to save a byte, I've encoded the instruction to exit the program into the
    ; low byte of the offset in the following instruction:
    lea si,[di+01c3h] 
    push si
l1: mov dx,bp
    mov ah,6
    int 21h
    jz l2
    mov bl,al
    shr byte ptr [di+bx],cl
    jz l1
    inc si
    mov [si],bx
    jmp l1
l2: pop si
l3: inc si
    mov bl,[si]
    cmp bl,bh
    je l0+2
    cmp [di+bx],cl
    jne l3
    mov dl,bl
    mov ah,2
    int 21h
    jmp l3

Assembles to 53 bytes. Reads standard input and writes results to standard output, eg:

 programname < input > output

C# (53 Characters)

Where s is your input string:

new string(s.Where(c=>s.Count(h=>h==c)<2).ToArray());

Or 59 with re-assignment:

var a=new string(s.Where(c=>s.Count(h=>h==c)<2).ToArray());

Haskell Pointfree

import Data.List
import Control.Monad
import Control.Arrow
main=interact$liftM2(\\)nub$ap(\\)nub

The whole program is 97 characters, but the real meat is just 23 characters. The rest is just imports and bringing the function into the IO monad. In ghci with the modules loaded it's just

(liftM2(\\)nub$ap(\\)nub) "nbHHkRvrXbvkn"

In even more ridiculous pointfree style (pointless style?):

main=interact$liftM2 ap liftM2 ap(\\)nub

It's a bit longer though at 26 chars for the function itself.

Shell/Coreutils, 37 Characters

fold -w1|sort|uniq -u|paste -s -d ''

sed, 41 chars

:;s/((.).*\2.*)\2/\1/;t;s/(.)(.*)\1/\2/;t

Usage: $ echo nbHHkRbvnrXbvkn | sed -r ':;s/((.).*\2.*)\2/\1/;t;s/(.)(.*)\1/\2/;t'

With contributions by gnarfpyon ;).

LilyPond, 78 chars

z=#(ly:gulp-file"A")#(print(string-delete z(lambda(x)(>(string-count z x)1))))

Usage: $ cp input.in A; lilypond this.ly

using C - 118 Characters

I think this answer is good as it will work for any string length.

main(int s,char *a[]){int i=0,j,c,d;while(s=c=a[1][i]){j=0;while(d=a[1][j])if(i!=j++)if(c==d)s=0;s&&putchar(c);i++;}}

and by removing the type defs of the variables, can get it down to 105 (new C winner i think :P) but my compiler is throwing errors with that!

What do you guys think?

D2 (templates): 195 197 199 + 17 characters

template F(alias s,int c,int i){static if(s>"")enum F=F!(s[1..$],c,i-(s[0]==c));else enum F=i?s:s~c;}template M(alias s,alias t=s){static if(s>"")enum M=F!(t,s[0],1)~M!(s[1..$],t);else enum M=s;}

Expanded:

template F(alias s,int c,int i){
    static if(s>"")
        enum F=F!(s[1..$],c,i-(s[0]==c));
    else
        enum F=i?s:s~c;
}
template M(alias s,alias t=s){
    static if(s>"")
        enum M=F!(t,s[0],1)~M!(s[1..$],t);
    else
        enum M=s;
}

pragma(msg,M!"nbHHkRvrXbvkn");

Lua, 97 Characters

i=...repeat c=i:match("(.).-%1")i=c and i:gsub(c:gsub("(%W)","%%%1"),"")or i until not c print(i)

The D programming language version 2, 68 characters:

auto f(S)(S s){return array(filter!((a){return s.count(a)<2;})(s));}

F#, Non-Code-Golf version using lists:

16 ilnes using lists:

let rec removefromlist v l = 
    match l with 
    | h::t -> 
        let (res, removed) = removefromlist v t
        if h = v then (res, true)
        else (h::res, removed)
    | [] -> ([], false)
let rec removedups unique tail = 
    match tail with
    | h::t -> 
        let (u_res, u_removed) = removefromlist h unique
        let (t_res, t_removed) = removefromlist h t
        if (t_removed || u_removed) then removedups u_res t_res
        else h::removedups u_res t_res
    | [] -> []
removedups [] (Array.toList("nbHHkRvrXbvkn".ToCharArray()));;

F# - 185 characters - More terse version without lists:

let s = "nbHHkRvrXbvkn"
let n c (s:string)=
    let mutable i = 0
    for x in 0..s.Length-1 do
        if s.[x]=c then i<-i+1
    i
String.collect (fun c -> if n c s>1 then "" else c.ToString()) s

GW-BASIC - 117 chars

1INPUT I$:FOR I=1 TO LEN(I$):S$=MID$(I$,I,1):C=0
2P=INSTR(P+1,I$,S$):C=C-(P>0):IF P GOTO 2
3IF C=1 THEN ?S$;
4NEXT

ASL: 23

args1[;{},,\=/+1=]""z P

ASL is a Golfscript inspired scripting language I made.

Related