Precompute the prefix 2D array
for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ MAX_CHAR ; $ j ++ ) $ l [ $ j ] [ $ i ] += $ l [ $ j ] [ $ i - 1 ] ; $ l [ ord ( $ s [ $ i ] ) - ord ( ' a ' ) ] [ $ i ] ++ ; } $ r [ ord ( $ s [ $ n - 1 ] ) - ord ( ' a ' ) ] [ $ n - 1 ] = 1 ;