# Detriplicate a string

A lot of languages have built-in ways to get rid of duplicates, or "deduplicate" or "uniquify" a list or string. A less common task is to "detriplicate" a string. That is, for every character that appears, the first two occurrences are kept.

Here is an example where the characters that should be deleted are labelled with ^:

aaabcbccdbabdcd
^    ^ ^^^ ^^
aabcbcdd

## Rules

Input is a single, possibly empty, string. You may assume that it only contains lowercase letters in the ASCII range.

Output should be a single string with all characters removed which have already appeared at least twice in the string (so the left-most two occurrences are kept).

Instead of strings you may work with lists of characters (or singleton strings), but the format has to be consistent between input and output.

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

## Test Cases

Every pair of lines is one test case, input followed by output.

xxxxx
xx
abcabc
abcabc
abcdabcaba
abcdabc
abacbdc
aaabcbccdbabdcd
aabcbcdd

The Stack Snippet at the bottom of this post generates a leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 3 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

• Singleton strings... stringletons? Jul 28 '16 at 19:00

# Jelly, 6 bytes

Qx2œ&@

### How it works

Qx2œ&@  Main link. Argument: s (string)

Q       Unique; deduplicate s.
x2     Repeat each character.
œ&@  Take the multiset intersection of s and the previous result.

# JavaScript (ES6), 42 48

Edit A whopping 6 bytes saved thx @Neil

s=>s.replace(k=/./g,c=>(k[c]+=c)[11]?'':c)

Explanation: I use the properties 'a'...'z' of object k to store info for each character (object k is a regexp in this case just to save bytes). These properties are initially undefined. In javascript adding a number to undefined gives NaN (quite sensible), but adding a string 'X' gives "undefinedX" - a string of length 10 (silly). Adding more characters you get longer strings. If the obtained string for a given character is longer than 11, that character is not copied to output.

Test

F=
s=>s.replace(k=/./g,c=>(k[c]+=c)[11]?'':c)

test=

xxxxx
xx
abcabc
abcabc
abcdabcaba
abcdabc
abacbdc
aaabcbccdbabdcd
aabcbcdd.split\n
for(i=0;i<test.length;)
a=test[i++],b=test[i++],r=F(a),
console.log(r==b?'OK':'KO',a,'->',r,b)

• Strictly speaking an empty line is one of the test cases.
– Neil
Jul 26 '16 at 12:28
• @Neil ok added the empty string test Jul 26 '16 at 14:40
• If you switch to array input and output, you can use .filter to save 12 more characters. v=>v.filter(x=>!(v[x]+=x)[11]). Kudos on the "undefined" hack. Jan 31 '17 at 18:57
• @Grax thanx but too different. Should post it yourself Jan 31 '17 at 20:32

## Python 2, 48 bytes

lambda s:reduce(lambda r,c:r+c*(r.count(c)<2),s)

c[r.count(c)/2:] is a same-length alternative to c*(r.count(c)<2) .

49 bytes:

r=''
for c in input():r+=c*(r.count(c)<2)
print r

# Retina, 17 bytes

(.)(?<=\1.*\1.+)

Try it online!

Simple regex replace - match a character if it already appeared twice, and remove it.

• I also tried a loop, and a repeated group with {2}, both with 18 bytes.
– Kobi
Jul 25 '16 at 10:54
• I've got 14 using a recently added feature. ;) Jul 25 '16 at 10:56
• I knew there was something. I looked at limits, probably not that one. I'll check again.
– Kobi
Jul 25 '16 at 11:02
• Ah, I think I found Martin's answer. I had some trouble when I was trying before, I think because I didn't consider how deduplicate would work on a multi-line input. Spoiler (with 5 bytes added to enable per-line mode): retina.tryitonline.net/… Jul 25 '16 at 12:57
• @FryAmTheEggman - Nice, I didn't find this one. Feel free to add an answer - I think this is too different from my answer and I didn't feel comfortable editing it in :P. Thanks!
– Kobi
Jul 28 '16 at 14:20

# Brachylog, 25 bytes

.v|s.g:.z:1a
:2fl<3
he~t?

### Explanation

This works because s - Subset will unify with bigger subsets first, thus e.g. for "aaa" it will try "aa" before "a".

• Main predicate:

.v         input = Output = ""
|          Or
s.         Output is an ordered subset of the input
g:.z       Zip each character of the output with the output itself
:1a        Apply predicate 1 on each element of the zip

• Predicate 1: Check that all characters only appear at most twice. Input = [String:Char]

:2f        Find all valid outputs of predicate 2 (i.e. one output per occurence
of the char)
l<3        There are less than 3 occurences

• Predicate 2: Get an occurence of a character. Input = [String:Char]

he         Take a character of the string in the input
~t?      That character is the char of the input

## ><>, 22 bytes

i:0(?;::9g:}2(?o{1+$9p Try it online! Uses the codebox to keep track of counts so far. i Read a char c of input :0(?; Halt if EOF : Make a copy - stack has [c c] at the top :9g Get count stored at (c, 9) :} Copy the count and move to bottom of stack 2(?o If the count is less than 2, output c {1+ Move the count back to the top of the stack and increment$9p  Update cell at (c, 9)
[Instruction pointer moves to start as ><> is toroidal]

## J, 20 15 bytes

#~(3>[+/@:={:)\

This defines a monadic function that takes and returns a string. Try it here. Usage:

f =: #~(3>[+/@:={:)\
f 'abaacbb'
abacb

## Explanation

I switched to the same algorithm that some other solutions use, since it turned out to be shorter...

#~(3>[+/@:={:)\  Input is y.
(          )\  For each prefix of y:
=        compute the equality vector
[     {:      of the prefix and its last element, and
+/@:         take its sum. Now we have a vector r such that y[i] has its
r[i]'th occurrence at position i.
3>              Mark those coordinates where r[i] < 3.
#~               Remove the non-marked characters from y.

foldl(\s c->s++[c|filter(==c)s<=[c]])""

Usage example: foldl(\s c->s++[c|filter(==c)s<=[c]])"" "aaabcbccdbabdcd" -> "aabcbcdd".

Keep the next char c if the string of all cs so far are lexicographical less or equal the singleton string [c].

Edit: @xnor saved a byte by switching from list comprehension to filter. Thanks!

• Your alternative could do filter(==c)s<=[c] to save a byte.
– xnor
Jul 25 '16 at 21:23

## Perl, 22 bytes

21 bytes code + 1 for -p.

aabcbcdd

# C, 57 bytes

Call f() with the string to detriplicate. The function modifies its parameter. Requires C99 because of the for-loop declaration.

f(char*p){for(char*s=p,m[256]={0};*s=*p;s+=++m[*p++]<3);}
• Can't you put the declaration of s into the first statement of the for? Jul 25 '16 at 14:00
• In C99 you can. I just didn't because I like to keep golfs C89 compatible. Jul 25 '16 at 14:39

# JavaScript (ES6), 35 bytes

s=>s.filter(c=>(s[c]=(s[c]|0)+1)<3)

Takes an array of characters as input and returns the detriplicated array.

• Nice. You could do c=>(s[c]=-~s[c])<3 to save a few bytes. Jan 18 '17 at 17:13
• I'd missed that you could use arrays as input and had written a function using map. Golfed it looked essentially like yours. the main difference was the assignment, which if you'll switch it around will save a few bytes. Try s.filter(c=>(s[c]=s[c]+1|0)<3) for 33 bytes. EDIT: Whoops, missed the comment above me, that's even better :)
– Jan
Feb 7 '17 at 18:34

## PowerShell v2+, 31 bytes

Creates a helper array $b pre-populated with 0s. Casts the input string$args[0] as a char-array, pipes it through a loop |%{...}. Each iteration outputs the current character $_ as a string "$_" multiplied by a Boolean that is only $TRUE (implicitly cast to 1 here) if the appropriate point in the helper array is less than 2 (i.e., we haven't seen this char twice already). The resultant collection of strings is encapsulated in parens and -joined together to form a single output string. That's left on the pipeline and output is implicit. • regex is unbeatable. :) I beleave a hashtable is better then an array for the variant without regex:$b=@{};-join($args|% t*y|?{++$b.$_-lt3}). Sep 10 '18 at 13:26 • @mazzy For the variant without regex and your code, it would need to be a newer version than PowerShell 2. As a result, I think I'll keep this answer without change. You can post your code as a separate answer, though! Sep 10 '18 at 17:46 • did the hashtable appear in the version 3.0? Ok. Thanks. Sep 10 '18 at 17:50 # Mathematica, 39 bytes Fold[If[Count@##<2,Append@##,#]&,{},#]& Anonymous function. Takes a character list as input, and returns the detriplicated list as output. Uses the method of folding over the list and rejecting triplicate elements, it's not too complicated. ## 05AB1E, 12 bytes vyˆ¯y¢O3‹iy? Explanation v # for each char in input yˆ # push to global array ¯y¢O3‹i # if nr of occurrences are less than 3 y? # print it Try it online # MATL, 8 bytes t&=Rs3<) Try it online! ### Explanation t % Input string implicitly. Push another copy &= % Matrix of all pairwise equality comparisons of string elements R % Keep only upper triangular part, making the rest of the entries zero s % Sum of each column. This gives a vector with number of occurrences % of the current character up to the current position 3< % True for entries that are less than 3 ) % Use as logical index into initial copy of the input. Display implicitly ### Example Assuming input 'aaababbc', the stack contains the following after the indicated statements: • t 'aaababbc' 'aaababbc' • t&= 'aaababbc' [ 1 1 1 0 1 0 0 0; 1 1 1 0 1 0 0 0; 1 1 1 0 1 0 0 0; 0 0 0 1 0 1 1 0; 1 1 1 0 1 0 0 0; 0 0 0 1 0 1 1 0; 0 0 0 1 0 1 1 0; 0 0 0 0 0 0 0 1 ] • t&=R 'aaababbc' [ 1 1 1 0 1 0 0 0; 0 1 1 0 1 0 0 0; 0 0 1 0 1 0 0 0; 0 0 0 1 0 1 1 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 1 1 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 1 ] • t&=Rs 'aaababbc' [ 1 2 3 1 4 2 3 1 ] • t&=Rs3< 'aaababbc' [ true true false true false true false true ] • t&=Rs3<) 'aabbc' ## Retina, 14 bytes D(.)(?<=\1.*) Verify all test cases. (The % enables per-line mode) Uses the new "Deduplicate" stage to save a couple bytes over Kobi's approach. Deduplicate gathers a list of all matches to the regex and replaces all but the first with the empty string. The regex matches a character that already appears once in the string, meaning that the first two will be kept. ## K, 18 Bytes g:{x{?x@<x}@,/2#'=x} g "abc" "abc" g "aaabcbccdbabdcd" "aabcbcdd" /k4 request test vectors from internet R:"GET /raw/ftHe0bpE HTTP/1.0\r\nHost: pastebin.com\r\n\r\n" t:+0N 2#t@1_&|\(0=#:)'t:1_"\r\n"\::http://pastebin.com:80 R /k4 no internet? use a file called "t.txt" in current directory t:+0N 2#0:`:t.txt /k6? t:+0N 2#0:"t.txt" /visually inspect test cases g't[0] (();"xx";"abcabc";"abcdabc";"abacbdc";"aabcbcdd") /do all tests pass? |/ t[1] {$[0=#x;0=#y;x~y]}' g't[0]
1b

It may be easiest to see this broken apart, but first some syntax: g:x sets g to x. {x+1} is a function which takes an argument x. In K the first argument to a function is x (the second is y and the third is z. Don't need a fourth).

Now:

x:"aaabcbccdbabdcd"

=x means group x, which produces:

"abcd"!(0 1 2 10;3 5 9 11;4 6 7 13;8 12 14)

2#' means two taken(from) each which produces

"abcd"!(0 1;3 5;4 6;8 12)

As you can see, these are the offsets of the first two matches of each character. The 2 could be generalised.

,/ means join each and is often called raze. It's going to get us just the values of our dictionary. Thus, ,/"abcd"!(0 1;3 5;4 6;8 12) produces:

0 1 3 5 4 6 8 12

which we need to sort. {x@<x}@ is an idiom K programmers often see (Q calls it asc), which says x at grade-up x. Breaking it apart:

<0 1 3 5 4 6 8 12
0 1 2 4 3 5 6 7

returned the indices of the sorted array, which we want taken from the original array. x@y means x at y so this indexes the array with the indices of the sort (if that makes any sense).

{x@<x}@0 1 3 5 4 6 8 12
0 1 3 4 5 6 8 12

which we simply now index into our original array. We could say x@ here, but K supports a really powerful concept which we can take advantage of here: function application is indexing. That means that a[0] could be looking up the zeroth slot of a or it could be applying the 0 to the function called a. The reason we needed the @ previously in {x@<x} is because x<y means xs less than ys: Operators in K have a dyadic form (two-argument) and a monadic form (one-argument) that comes from APL. Q doesn't have this "ambivalence".

• Welcome to PPCG! Great first answer. :) Jul 31 '16 at 8:06
• I have a couple of questions. 1. Is K4 the same language as the one you link to (Q/kdb+)? 2. Could you show how to call your function on an input or how the items in testVectors.txt should be formatted? Aug 1 '16 at 6:45
• @Dennis 1. Yes. Press backslash to get from Q to K. 2. Just as they appear in the question: pastebin.com/ftHe0bpE example call: g"aaabcbccdbabdcd" Aug 1 '16 at 9:23
• OK, thanks. Couldn't get the file part working, but g"..." does the trick. Unfortunately, your code returns aabbcc for input abc. Aug 1 '16 at 15:28
• @Dennis You might have done something wrong: {x{?x@<x}@,/2#'=x}"abc" definitely returns "abc". It would return "aabbcc" if you missed the ? distinct. Aug 1 '16 at 15:43

F~kR/2<Ii?+k(K~k

Try it here!

# Python 2, 51 bytes

f=lambda s:s and f(s[:-1])+s[-1]*(s.count(s[-1])<3)

Test it on Ideone.

## Java 8 lambda, 90 characters

i->{int[]o=new int[128];String r="";for(char c:i.toCharArray())if(++o[c]<3)r+=c;return r;}

Ungolfed version:

public class Q86503 {

static String detriplicate(String input) {
int[] occurences = new int[128];
String result = "";
for (char c : input.toCharArray()) {
if (++occurences[c] < 3) {
result += c;
}
}
return result;
}
}

Creates an array for all ascii characters. If a character occurs the corresponding counter will be increased. If it is over 2 the character won't be appended to the result string. Very easy, very short ;)

# Perl 6, 27 bytes

{.comb.grep({++%.{$_} <3})} Explanation: {.comb.grep({++%.{$_} <3})}
{                         } # a function
.comb                      # get all the characters in the argument
.grep({           })  # filter
%.           # an anonymous hash (shared between calls to grep)
++  {$_} # increment the value at the current key (current letter). # if the key doesn't exist, it defaults to 0 (then gets incremented) <3 # return True if it wasn't seen 3 times (Note: Perl 6 isn't as "golf-oriented" as its sister Perl 5 ... So yes, that space before the < is necessary. The %.{} is an anonymous hash). • 24 bytes – Jo King Sep 8 '18 at 9:25 # SmileBASIC, 777269 68 bytes DIM R[#Y]READ S$WHILE""<S$Q=ASC(S$)INC R[Q]?SHIFT(S$)*(R[Q]<3); WEND Explained: DIM R[128] 'array to store letter frequencies READ S$ 'get input string
WHILE""<S$'much shorter than LEN(S$)
Q=ASC(S$) 'get ascii value of first character in S$
INC R[Q]
?SHIFT(S$)*(R[Q]<3); 'remove the first character of S$, and print it if there are less than 3 occurrences.
WEND
• Welcome to ppcg! Nice first post! Jan 24 '17 at 5:09

## Common Lisp, 127

(lambda(s)(map()(lambda(x)(flet((p(b)(1+(position x s :start b))))(setf s(remove x s :start(p(p 0))))))(remove-duplicates s))s)

### Pretty-printed

(lambda (s)
(map nil
(lambda (x)
(flet ((p (b)
(1+ (position x s :start b))))
(setf s (remove x s :start (p (p 0))))))
(remove-duplicates s))
s)

## Q, 52 Bytes

q)f2:{x asc raze{distinct 2#where x}each x~'/:distinct x}
q)f2 each testList
"xx"
"abcabc"
"abcdabc"
"abacbdc"
"aabcbcdd"
q)

## K, 27 Bytes

f:{x{x@<x}@,/{?2#&x}'x~'/:?x}
f'testList
("xx";"abcabc";"abcdabc";"abacbdc";"aabcbcdd")

# Ruby, 7962 57 bytes

This is pretty unwieldy, but I'm not sure I can golf this much better at the moment. Any golfing suggestions are welcome. Try it online!

Edit: -17 bytes thanks to Value Ink by suggesting a golfier way to remove triplicate characters. -5 bytes from removing the .uniq method.

->s{s.chars.map{|a|s[s.rindex a]=""while s.count(a)>2};s}

Ungolfed:

def g(s)
s.chars.each do |a|
while s.count(a) > 2
i = s.rindex(a)
s[i] = ""
end
end
return s
end
• 62 bytes: ->s{s.chars.uniq.map{|a|s[s.rindex a]=""while s.count(a)>2};s} Jan 24 '17 at 5:03

# JavaScript, 30 bytes

v=>v.filter(x=>!(v[x]+=x)[11])

Using the method that @edc65 came up with for counting but with an array filter. First time character appears, the object value gets "undefined" plus the character (i.e. "undefinedx"). The next time the object value becomes "undefinedxx".

After that, v[x][11] returns true and when combined with the not operator, false, meaning characters that have already appeared twice will be filtered.

# Kotlin, 50 bytes

{it.filterIndexed{i,c->it.take(i).count{it==c}<2}}

Try it online!

# PHP, 42 bytes

Loop through the string, count each character in an array, only echo if the letter hasn't reached a count of 3 yet.

while($e=$argn[$x++])if($s[$e]++<2)echo$e;

Try it online!

• Nice answer! You can save a couple of bytes using${$e} instead of $s[$e] and using the && shortcircuit too! Try it online! Dec 16 '21 at 15:56

# C (gcc), 85 bytes

int f(char*i){int v[255]={};int x,y;x=y=0;do++v[i[x]]<3?i[y++]=i[x]:0;while(i[x++]);}

Try it online!

de-golfed version:

int f(char* i)
{
int v[255]={};
int x,y;
x=y=0;
do
{
++v[i[x]]<3?i[y++]=i[x]:0;
}while(i[x++]);
}

Takes input as an array of characters and outputs by updating it in-place.

• You can remove the return type declaration of f, and combine the declarations of v with x and y: Try it online! Dec 16 '21 at 3:15
• Can save even more with for over do while and eliminating one of x/y: Try it online!
– att
Dec 16 '21 at 6:31