In place sorting of a string to find out if there are non-unique characters

Question

Recently I came across a problem that asks to find out the non-unique characters in a string without any additional buffer. I interpreted this problem to be an in-place sort of the characters in the string and then iterating through it in order to track down the non-unique characters.

Another solution that can have O(1) space and O(n^2) run-time is having two 'for' loops going over the string to track down any pairs of characters that are common.

What I need is to sort the string in atleast O(nlogn) time with O(1) space.

Is there a simple/elegant way to do an in-place sort of characters in O(nlgn) with O(1) space?

Answer 1

There is a really nice comparison grid of sorting algorithms on wikipedia.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Heapsort and Smoothsort seem to be your obvious winners. Depending on your language you may or may not already have these, though I'm sure in most cases they're probably a library away.

There's a Java impl that at a glance claims to heapsort a set of anything Comparable.
http://www.java-tips.org/java-se-tips/java.lang/heap-sort-implementation-in-java.html

Answer 2

How about, rather than sorting, just scanning the string to find the characters that occur more than once? You can use 256 bits to keep track of which characters occur once, and an additional 256 bits to keep track of the characters that occur at least twice. Total extra memory usage is 512 bits, just 16 32-bit words, and the algorithm runs in linear time, and does not modify the original string.

Answer 3

Shell Sort.