# 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: