If you can assume the string will be ASCII chars then you could get purely O(n) time and O(1) space using 1 for loop, 2 bitsets of size: unsigned char bitset[32] and a length variable int len = 0;. Check each char in its position in the seenBitset, if 0, len++ and set the bit, next char. If seen bit is 1, check oddBitset, if odd bit is 0, len++, toggle odd bit, if 1, len- -, toggle odd bit. Finish loop and return len. This should work cuz really all you need to know is if it’s a new character and if the total repeats are even or odd. Both can be represented with a Boolean value. And no need to loop back through to total the number of characters. Just use one running count to accumulate the resulting length and return it at the end :)

In C++, I sorted the array and then compared each word in the array with the remaining words in the array by using Rabin Karp instead of KNP. For some reason Rabin Karp comes easier to me than KNP.

Good Explanation