Detriplicate a string

Question

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

Your task is to implement exactly this operation.

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 code-golf, 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
abacbadcba
abacbdc
aaabcbccdbabdcd
aabcbcdd

Leaderboard

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.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

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

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 86503; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 8478; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

Answer 1

Jelly, 6 bytes

Qx2œ&@

Try it online! or verify all test cases.

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.

Answer 2

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

Answer 3

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

Answer 4

Retina, 17 bytes

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

Try it online!

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

Answer 5

Brachylog, 25 bytes

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

Try it online! or verify all test cases.

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
  

Answer 6

><>, 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]

Answer 7

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.

Answer 8

Haskell, 40 39 bytes

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!

Answer 9

Perl, 22 bytes

21 bytes code + 1 for -p.

s/./$&x(2>${$&}++)/ge

Usage

perl -pe 's/./$&x(2>${$&}++)/ge' <<< 'aaabcbccdbabdcd'
aabcbcdd

Answer 10

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

Answer 11

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.

Answer 12

PowerShell v2+, 31 bytes

$args-replace'(.)(?<=\1.*\1.+)'

Uses the same regex as in Kobi's Retina answer, just encapsulated in the PowerShell -replace operator. Works because both are using .NET-flavor regex in the background.

Alternatively, without regex, 56 bytes

$b=,0*200;-join([char[]]$args[0]|%{"$_"*($b[$_]++-lt2)})

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.

Answer 13

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.

Answer 14

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

Answer 15

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'
  

Answer 16

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.

Answer 17

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

K4 is available for free download; K6 is in development. If you've downloaded KDB, you can get into K with backslash.

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

Answer 18

Pyke, 16 bytes

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

Try it here!

Answer 19

Python 2, 51 bytes

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

Test it on Ideone.

Answer 20

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

Answer 21

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

Answer 22

SmileBASIC, 77 72 69 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

Answer 23

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)

Answer 24

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)

Answer 25

K, 27 Bytes

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

Answer 26

Ruby, 79 62 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

Answer 27

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.

Answer 28

Kotlin, 50 bytes

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

Try it online!

Answer 29

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!

Answer 30

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.