For simplicity , 1 extra space is used in all below arrays extras [ i ] [ j ] will have number of extra spaces if words from i to j are put in a single line
extras = [ [ 0 for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE