# Append and erase

Given one line that consists of only letters, process as following:

• You maintain a string that's empty at the beginning.
• If the next input character is in the string, remove it from the string.
• If the next input character isn't in the string, append it to the string.

Output the final state of the string.

You can safely assume the input consists at least one character (i.e. non-empty), but there's no guarantee that the output isn't empty.

Pseudocode (Feel free to golf this):

str = EMPTY
for each character ch in input
if ch exists in str
remove all ch from str
else
append ch to str
print str


The input matches the regular expression ^[A-Za-z]+$. Sample test cases: ABCDBCCBE -> ADCBE ABCXYZCABXAYZ -> A aAABBbAbbB -> aAbB GG -> (empty)  The input can be given in any applicable way, but it must be treated as a string, and the same for output. The program should not exit with an error. The shortest program in each language wins! Extra (Optional): Please explain how your program works. Thank you. • May the line be empty? Nov 28 '17 at 15:37 • @user202729 No. I changed a little (it does not invalidate any answer) so the input is never empty. – iBug Nov 28 '17 at 16:03 • So why did you reject ais523's edit suggestion (link)? Nov 28 '17 at 16:09 ## 35 Answers # PHP, 71+1 bytes while(~$c=$argn[$i++])$s=strstr($s,$c)?strtr($s,[$c=>""]):$s.$c;echo$s;


Run as pipe with -nR or try it online.

# Python 3.6, 69 bytes

lambda a:"".join({c:1 for c in a[::-1] if a.count(c)%2}.keys())[::-1]


Try it online!

Dict insertion order is preserved in Python 3.6 .

# SNOBOL4 (CSNOBOL4), 97 95 bytes

	S =INPUT
N	S LEN(1) . C REM . S :F(O)
O C :S(R)
O =O C :(N)
R	O C =:S(R)F(N)
O	OUTPUT =O
END


Try it online!

	S =INPUT			;* read input
N	S LEN(1) . C REM . S :F(O)	;* take the first character of S and assign it to C,
;* assign the remainder to S, and if S has no characters left, goto O
O C :S(R)			;* if C matches anything in O, goto R, otherwise go to next line
O =O C :(N)			;* append C to O and goto N
R	O C =:S(R)F(N)			;* as long as C matches O, replace it with ''
;* (unassigned variables default to the null string)
;* then goto N once it fails to match
O	OUTPUT =O			;* output the string
END					;* terminate the program


# Julia 0.6, 49 bytes

~x=foldl((s,c)->in(c,s)?replace(s,c,""):s*c,"",x)


Try it online!

Algorithm from the pseudocode. This does not work like this in tio.run because concatenation of a string with a char using * is not defined. It does work in JuliaPro 0.6.1.1 however, where this is defined from the future™ (0.7 dev).

# C (gcc), 95 94 bytes

char*f,*g,c[256];F(char*s){for(f=s;*f;++c[*f++]);for(g=f;f>=s;--f)c[*f]&1?c[*g--=*f]=0:0;++g;}


Try it online!

char *F(char *src);


The input is a null terminated string. It must be writeable.

The output is a pointer to the middle of the source string containing the filtered string (done with the return hack). It will also be null terminated.

Uses a similar approach to djhurio's second answer and coltim's answer, where I count the characters, then select only the last characters that appear once.

It is the only viable option, you can't just "remove" a character in C, and there are no fancy builtins that do anything close to what the other algorithms do.

However, unlike those two, I do everything manually because it is torture fun, and I modify the string in place without reversing it.

I initially tried doing something in C++ with <algorithm>, but std::remove_if moves forwards, meaning we would have to std::reverse twice.

char *append_and_erase(char *src)
{
// Temp variables
char *f, *g;
// Buffer to hold our character count.
char counts[256] = { 0 };

// Count the occurrences of each character.
for (f = src; *f != '\0'; f++)
++counts[*f];

// Go backwards in the string, writing all the characters that appeared an
// odd number of times, and skipping the ones that repeat.
//
// It is basically a backwards std::remove_if.
//
// g will point to the start of the trimmed string minus one.
// It will look like this:
//    garbageABCDEFG\0
//    ^src  ^g
// g will be off by one, so we need to increment it before we are done.
for (g = f; f >= src; --f) {
if (counts[*f] % 2 != 0) {
*g-- = *f;
// Clear the count so we don't have duplicates
counts[*f] = 0;
}
}
// More logical version:
//
//    f = src;
//    g++;
//    // strcpy but guaranteed to be forwards
//    while ((*f++ = *g++) != '\0');
//
// Golf version:
// Increment g and return it (we use the return hack in the golf)
return g + 1;
}


Thanks to ceilingcat for the -1 byte using a ternary.

• Thanks. I was so frustrated with operator precedence when trying to do && that I forgot about ternaries. 🤦‍♂️ Jan 4 at 14:27