15
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ May the line be empty? \$\endgroup\$
    – DELETE_ME
    Nov 28 '17 at 15:37
  • 1
    \$\begingroup\$ @user202729 No. I changed a little (it does not invalidate any answer) so the input is never empty. \$\endgroup\$
    – iBug
    Nov 28 '17 at 16:03
  • 1
    \$\begingroup\$ So why did you reject ais523's edit suggestion (link)? \$\endgroup\$
    – DELETE_ME
    Nov 28 '17 at 16:09

35 Answers 35

1
2
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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 .

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

Ungolfed version with comments:

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks. I was so frustrated with operator precedence when trying to do && that I forgot about ternaries. 🤦‍♂️ \$\endgroup\$
    – EasyasPi
    Jan 4 at 14:27
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.