Code Golf: Duplicate Character Removal in String

Question

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.)

Answer 1

LabVIEW 7.1

ONE character and that is the blue constant '1' in the block diagram. I swear, the input was copy and paste ;-)

http://i25.tinypic.com/hvc4mp.png

http://i26.tinypic.com/5pnas.png

Answer 2

Perl

21 characters of perl, 31 to invoke, 36 total keystrokes (counting shift and final return):

perl -pe's/$1//gwhile/(.).*\1/'

Answer 3

Ruby — 61 53 51 56 35

61 chars, the ruler says. (Gives me an idea for another code golf...)

  puts ((i=gets.split(''))-i.select{|c|i.to_s.count(c)<2}).join
+-------------------------------------------------------------------------+
||    |    |    |    |    |    |    |    |    |    |    |    |    |    |  |
|0         10        20        30        40        50        60        70 |
|                                                                         |
+-------------------------------------------------------------------------+
  gets.chars{|c|$><<c[$_.count(c)-1]}

... 35 by Nakilon

Answer 4

APL

23 characters:

(((1+ρx)-(ϕx)ιx)=xιx)/x

I'm an APL newbie (learned it yesterday), so be kind -- this is certainly not the most efficient way to do it. I'm ashamed I didn't beat Perl by very much.

Then again, maybe it says something when the most natural way for a newbie to solve this problem in APL was still more concise than any other solution in any language so far.

Answer 5

Python:

s=raw_input()
print filter(lambda c:s.count(c)<2,s)

This is a complete working program, reading from and writing to the console. The one-liner version can be directly used from the command line

python -c 's=raw_input();print filter(lambda c:s.count(c)<2,s)'

Answer 6

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.

Answer 7

Haskell

There's surely shorter ways to do this in Haskell, but:

Prelude Data.List> let h y=[x|x<-y,(<2).length$filter(==x)y]
Prelude Data.List> h "nbHHkRvrXbvkn"
"RrX"

Ignoring the let, since it's only required for function declarations in GHCi, we have h y=[x|x<-y,(<2).length$filter(==x)y], which is 37 characters (this ties the current "core" Python of "".join(c for c in s if s.count(c)<2), and it's virtually the same code anyway).

If you want to make a whole program out of it,

h y=[x|x<-y,(<2).length$filter(==x)y]
main=interact h

$ echo "nbHHkRvrXbvkn" | runghc tmp.hs
RrX

$ wc -c tmp.hs
54 tmp.hs

Or we can knock off one character this way:

main=interact(\y->[x|x<-y,(<2).length$filter(==x)y])

$ echo "nbHHkRvrXbvkn" | runghc tmp2.hs
RrX

$ wc -c tmp2.hs
53 tmp2.hs

It operates on all of stdin, not line-by-line, but that seems acceptable IMO.

Answer 8

C89 (106 characters)

This one uses a completely different method than my original answer. Interestingly, after writing it and then looking at another answer, I saw the methods were very similar. Credits to caf for coming up with this method before me.

b[256];l;x;main(c){while((c=getchar())>=0)b[c]=b[c]?1:--l;
for(;x-->l;)for(c=256;c;)b[--c]-x?0:putchar(c);}

On one line, it's 58+48 = 106 bytes.

C89 (173 characters)

This was my original answer. As said in the comments, it doesn't work too well...

#include<stdio.h>
main(l,s){char*b,*d;for(b=l=s=0;l==s;s+=fread(b+s,1,9,stdin))b=realloc(b,l+=9)
;d=b;for(l=0;l<s;++d)if(!memchr(b,*d,l)&!memchr(d+1,*d,s-l++-1))putchar(*d);}

On two lines, it's 17+1+78+77 = 173 bytes.

Answer 9

C#

65 Characters:

new String(h.Where(x=>h.IndexOf(x)==h.LastIndexOf(x)).ToArray());

67 Characters with reassignment:

h=new String(h.Where(x=>h.IndexOf(x)==h.LastIndexOf(x)).ToArray());

Answer 10

C#

new string(input.GroupBy(c => c).Where(g => g.Count() == 1).ToArray());

71 characters

Answer 11

PHP (136 characters)

<?PHP
function q($x){return $x<2;}echo implode(array_keys(array_filter(
array_count_values(str_split(stream_get_contents(STDIN))),'q')));

On one line, it's 5+1+65+65 = 136 bytes. Using PHP 5.3 you could save a few bytes making the function anonymous, but I can't test that now. Perhaps something like:

<?PHP
echo implode(array_keys(array_filter(array_count_values(str_split(
stream_get_contents(STDIN))),function($x){return $x<2;})));

That's 5+1+66+59 = 131 bytes.

Answer 12

another APL solution

As a dynamic function (18 charachters)

{(1+=/¨(ω∘∊¨ω))/ω}

line assuming that input is in variable x (16 characters):

(1+=/¨(x∘∊¨x))/x

Answer 13

VB.NET

For Each c In s : s = IIf(s.LastIndexOf(c) <> s.IndexOf(c), s.Replace(CStr(c), Nothing), s) : Next

Granted, VB is not the optimal language to try to save characters, but the line comes out to 98 characters.

Answer 14

PowerShell

61 characters. Where $s="nbHHkRvrXbvkn" and $a is the result.

$h=@{}
($c=[char[]]$s)|%{$h[$_]++}
$c|%{if($h[$_]-eq1){$a+=$_}}

Fully functioning parameterized script:

param($s)
$h=@{}
($c=[char[]]$s)|%{$h[$_]++}
$c|%{if($h[$_]-eq1){$a+=$_}}
$a

Answer 15

C: 83 89 93 99 101 characters

• O(n²) 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);}

)

Answer 16

Golfscript(sym) - 15

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

Answer 17

Haskell

(just knocking a few characters off Mark Rushakoff's effort, I'd rather it was posted as a comment on his)

h y=[x|x<-y,[_]<-[filter(==x)y]]

which is better Haskell idiom but maybe harder to follow for non-Haskellers than this:

h y=[z|x<-y,[z]<-[filter(==x)y]]

Edit to add an explanation for hiena and others:

I'll assume you understand Mark's version, so I'll just cover the change. Mark's expression:

(<2).length $ filter (==x) y

filters y to get the list of elements that == x, finds the length of that list and makes sure it's less than two. (in fact it must be length one, but ==1 is longer than <2 ) My version:

[z] <- [filter(==x)y]

does the same filter, then puts the resulting list into a list as the only element. Now the arrow (meant to look like set inclusion!) says "for every element of the RHS list in turn, call that element [z]". [z] is the list containing the single element z, so the element "filter(==x)y" can only be called "[z]" if it contains exactly one element. Otherwise it gets discarded and is never used as a value of z. So the z's (which are returned on the left of the | in the list comprehension) are exactly the x's that make the filter return a list of length one.

That was my second version, my first version returns x instead of z - because they're the same anyway - and renames z to _ which is the Haskell symbol for "this value isn't going to be used so I'm not going to complicate my code by giving it a name".

Answer 18

Javascript 1.8

s.split('').filter(function (o,i,a) a.filter(function(p) o===p).length <2 ).join('');

or alternately- similar to the python example:

[s[c] for (c in s) if (s.split("").filter(function(p) s[c]===p).length <2)].join('');

Answer 19

TCL

123 chars. It might be possible to get it shorter, but this is good enough for me.

proc h {i {r {}}} {foreach c [split $i {}] {if {[llength [split $i $c]]==2} {set r $r$c}}
return $r}
puts [h [gets stdin]]

Answer 20

Ruby

63 chars.

puts (t=gets.split(//)).map{|i|t.count(i)>1?nil:i}.compact.join

Answer 21

VB.NET / LINQ

96 characters for complete working statement

Dim p=New String((From c In"nbHHkRvrXbvkn"Group c By c Into i=Count Where i=1 Select c).ToArray)

Complete working statement, with original string and the VB Specific "Pretty listing (reformatting of code" turned off, at 96 characters, non-working statement without original string at 84 characters.

(Please make sure your code works before answering. Thank you.)

Answer 22

Scala

54 chars for the method body only, 66 with (statically typed) method declaration:

def s(s:String)=(""/:s)((a,b)=>if(s.filter(c=>c==b).size>1)a else a+b)

Answer 23

C

Full program in C, 141 bytes (counting newlines).

#include<stdio.h>
c,n[256],o,i=1;main(){for(;c-EOF;c=getchar())c-EOF?n[c]=n[c]?-1:o++:0;for(;i<o;i++)for(c=0;c<256;c++)n[c]-i?0:putchar(c);}

Answer 24

C

(1st version: 112 characters; 2nd version: 107 characters)

k[256],o[100000],p,c;main(){while((c=getchar())!=-1)++k[o[p++]=c];for(c=0;c<p;c++)if(k[o[c]]==1)putchar(o[c]);}

That's

/* #include <stdio.h> */
/* int */ k[256], o[100000], p, c;
/* int */ main(/* void */) {
  while((c=getchar()) != -1/*EOF*/) {
    ++k[o[p++] = /*(unsigned char)*/c];
  }
  for(c=0; c<p; c++) {
    if(k[o[c]] == 1) {
      putchar(o[c]);
    }
  }
  /* return 0; */
}

Because getchar() returns int and putchar accepts int, the #include can 'safely' be removed. Without the include, EOF is not defined, so I used -1 instead (and gained a char). This program only works as intended for inputs with less than 100000 characters!

Version 2, with thanks to strager 107 characters

#ifdef NICE_LAYOUT
#include <stdio.h>

/* global variables are initialized to 0 */
int char_count[256];                          /* k in the other layout */
int char_order[999999];                       /* o ... */
int char_index;                               /* p  */

int main(int ch_n_loop, char **dummy)         /* c  */
                                              /* variable with 2 uses */
{

  (void)dummy; /* make warning about unused variable go away */

  while ((ch_n_loop = getchar()) >= 0) /* EOF is, by definition, negative */
  {
    ++char_count[ ( char_order[char_index++] = ch_n_loop ) ];
    /* assignment, and increment, inside the array index */
  }
  /* reuse ch_n_loop */
  for (ch_n_loop = 0; ch_n_loop < char_index; ch_n_loop++) {
    (char_count[char_order[ch_n_loop]] - 1) ? 0 : putchar(char_order[ch_n_loop]);
  }
  return 0;
}
#else
k[256],o[999999],p;main(c){while((c=getchar())>=0)++k[o[p++]=c];for(c=0;c<p;c++)k[o[c]]-1?0:putchar(o[c]);}
#endif

Answer 25

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)

Answer 26

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

Answer 27

PHP

118 characters actual code (plus 6 characters for the PHP block tag):

<?php
$s=trim(fgets(STDIN));$x='';while(strlen($s)){$t=str_replace($s[0],'',substr($s,1),$c);$x.=$c?'':$s[0];$s=$t;}echo$x;

Answer 28

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());

Answer 29

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.

Answer 30

Shell/Coreutils, 37 Characters

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

Answer 31

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 ;).

Answer 32

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

Answer 33

Euphoria

165 characters from a pretty verbose language.

object c=getc(0),r={},b=r
while c>0 do
if find(c,r)then b&=c end if
r&=c
c=getc(0)
end while
for i=1 to length(r)do
if find(r[i],b)=0 then puts(1,r[i])end if
end for

Answer 34

sed/Java

A sed version with 30 characters, or 21 characters if you don't include the invocation of the command:

sed -r ':_;s/(.)(.*)\1/\2/;t_'

A java version using the same idea (should all be written in one line) which is 157 characters:

class T{public static void main(String[]a){String s=a[0];int l;
do{l=s.length();s=s.replaceAll("(.)(.*)\\1","$2");}while(s.length()<l);
System.out.printf(s);}}

Answer 35

Lua

98 char function, 115 char full program

f was written in the most readable format, and g aimed to reproduce f exactly but in a more terse manner.

Lowercase f and g functions are "verbose," and uppercase F and G are the "compressed" versions.

J is identical to G, but it is declared to show the necessary character count for a full program.

removedups.lua:

f = function(s)
    h=s:sub(1,1) -- head of string
    r=s:sub(2)   -- rest of string
    if r:find(h) then -- first character is repeated
        return f(s:gsub(h, '')) -- f(rest without any instance of h)
    elseif r > "" then -- there is something left in the rest of the string
        return h .. f(r) -- concatenate head with f(rest)
    else return h -- rest is empty string, so just return value left in head
    end
end

F=function(s)h=s:sub(1,1)r=s:sub(2)if r:find(h)then return f(s:gsub(h,''))elseif r>""then return h ..f(r)else return h end end
--       1         2         3         4         5         6         7         8         9        10        11        12
--3456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456
-- 126 chars, compressed

g = function(s)
    h=s:sub(1,1)
    r=s:sub(2)
    return (r:find(h) and g(s:gsub(h, '')) or (r > "" and h .. g(r)) or h)
end

G=function(s)h=s:sub(1,1)r=s:sub(2)return r:find(h)and g(s:gsub(h,''))or(r>""and h ..g(r))or h end
--       1         2         3         4         5         6         7         8         9        10        11     
--345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678
-- 98 chars, compressed

-- code-golf unit tests :)
assert(f("nbHHkRvrXbvkn")=="RrX")
assert(F("nbHHkRvrXbvkn")=="RrX")
assert(g("nbHHkRvrXbvkn")=="RrX")
assert(G("nbHHkRvrXbvkn")=="RrX")

J=function(s)h=s:sub(1,1)r=s:sub(2)return r:find(h)and g(s:gsub(h,''))or(r>""and h ..g(r))or h end print(J(arg[1]))
--       1         2         3         4         5         6         7         8         9        10        11     
--34567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345
-- 115 chars, full program

Output:

$ lua removedups.lua nbHHkRvrXbvkn
RrX

Answer 36

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?

Answer 37

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");

Answer 38

Lua, 91 characters

i,s=1,...s:gsub('.',function(c)if s:find(c,i)then s=s:gsub(c,'')else i=i+1 end end)print(s)

Answer 39

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)

Answer 40

The D programming language version 2, 68 characters:

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

Answer 41

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

Answer 42

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

Answer 43

OCaml, 93 characters (wc -c).

open String
let f s=let r=ref""in iter(fun c->if not(contains!r c)then r:=!r^(make 1 c))s;!r

Answer 44

#!/usr/bin/python

# Python, 67 characters, in a giant generator.
f=lambda s:''.join([c for c in s if len([d for d in s if d==c])<2])

string = "nbHHkRvrXbvkn"
print f(string) => "RrX"

Answer 45

F#, 94 chars

let f(a:string)=new string(Seq.toArray(Seq.filter(fun(c:char)->a.IndexOf c=a.LastIndexOf c)a))
printfn "%s" (f "nbHHkRvrXbvkn")

Answer 46

Python, 50 chars (based on SHiNKiROU 67 char version)

f=lambda s:''.join([c for c in s if s.count(c)<2])

Answer 47

ASL: 23

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

ASL is a Golfscript inspired scripting language I made.

Answer 48

I couldn't find the original answer, but in the spirit of a Jon Skeet answer:

Strip:

RSP

The meaning of this program is: Read a string from standard input (R), Strip all duplicate characters (S), Print the result to stdout (P).