I used a map to track number of occurrences of each character and removed a character on each even occurrence of the current character in a given iteration. At first I was concatenating the strings, when asked if there were performance issues with my approach for long strings I changed to a string buffer.