Precompute the prefix 2D array
for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( MAX_CHAR ) : NEW_LINE INDENT l [ j ] [ i ] += l [ j ] [ i - 1 ] NEW_LINE DEDENT l [ ord ( s [ i ] ) - ord ( ' a ' ) ] [ i ] += 1 NEW_LINE DEDENT r [ ord ( s [ n - 1 ] ) - ord ( ' a ' ) ] [ n - 1 ] = 1 NEW_LINE