サマーインターン2011問題

今年のインターン2011の応募者には書類選考後に次の問題を解いてもらいました。

長さnの文字列中で出現回数が最大の文字をO(n)時間で答えるプログラムを書いてください。但し、出現回数が最大の文字の出現回数はn/2より大きいとします。
条件として、文字列を格納しているバッファは書き換え可能で文字列以外に利用できるバッファサイズはc log n bits (cは任意の定数）であり、文字種類数は可変（最大n)であるとします。

#これはオプション問題で、解けなくても選考としては問題ありませんでした。
#指摘を受けまして、バッファサイズの条件をきちんと書きました。計算量はlog nビットのRAMモデル（連続するlog nビットの操作は定数時間）で考えています。

例えば、単純に各文字毎に頻度を数えるのにはバッファサイズが定数ですので記録できませんし、文字をソートするのもO(n log n)時間必要なので条件を満たしません。

これに対する正しい回答はこれまで３通り分かっています。
興味のある方は考えてみてください。