Programming puzzle: Surpassers

Difficulty: Hard

I was recently reading Pearls of Functional Algorithm Design by Richard Bird. One of the algorithms described is for detecting surpassers, I’ll explain what that is in a second. He presents an algorithm for solving this in O(n log n) time. However, if we add a tiny assumption we can improve this quite a bit to O(n) time and O(log n) space.

Surpasser

In a string, a surpasser is a character from later in the alphabet appearing later in the string. The surpasser count is the number of surpassers a character has. Here is a string with all the surpasser counts annotated below each character:

GENERATING
5625140100

The maximum surpasser count is six; The first occurrence of letter E has six surpassers, namely N, R, T, I, N, and G.

Puzzle

We can safely assume that we have a constant alphabet. The task is to find the maximum surpasser count using O(n) time and O(log n) space.

Implemented in Java this code should print 6:

public static void main(String[] args) {
  System.out.println(surpassers("GENERATING"));
}

If you like working with code you might like my refactoring book: