Construct a count array where value at every index contains count of smaller characters in whole string
function populateAndIncreaseCount ( & $ count , $ str ) { global $ MAX_CHAR ; for ( $ i = 0 ; $ i < strlen ( $ str ) ; ++ $ i ) ++ $ count [ ord ( $ str [ $ i ] ) ] ; for ( $ i = 1 ; $ i < $ MAX_CHAR ; ++ $ i ) $ count [ $ i ] += $ count [ $ i - 1 ] ; }