Word Wrap Problem

[riddhi-jain]

Given an array of size n, which denotes the number of characters in one word, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly. Assume that the length of each word is smaller than the line width. When line breaks are inserted there is a possibility that extra spaces are present in each line. The extra spaces includes spaces put at the end of every line except the last one. You have to minimize the following total cost where total cost = Sum of cost of all lines, where cost of line is = (Number of extra spaces in the line).

Example 1:

Input: nums = {3,2,2,5}, k = 6
Output: 4

Explanation: Given a line can have 6
characters,
Line number 1: From word no. 1 to 1
Line number 2: From word no. 2 to 3
Line number 3: From word no. 4 to 4
So total cost = (6-3) + (6-2-2+1) = 3+1 = 4.
As in the first line word length = 3 thus
extra spaces = 6 - 3 = 3 and in the second line
there are two word of length 2 and there already 1
space between two word thus extra spaces
= 6 - 2 -2 -1 =1.As mentioned the problem description
there will be no extra spaces in the last line.