Word Wrap

Moderate

0/80

Average time to solve is 20m

Contributed by

83 upvotes

Asked in companies

Problem statement

You are given ‘N’ words of various lengths, now you have to arrange these words in such a way that each line contains at most ‘M’ characters and each word is separated by a space character. The cost of each line is equal to the cube of extra space characters required to complete ‘M’ characters in that particular line. Total cost is equal to the sum of costs of each line.

Your task is to form this arrangement with the minimum cost possible and return the minimum total cost.

Note:

The length of each word should be less than or equal to ‘M’.

You can’t break a word, i.e. the entire word should come in the same line and it must not be the case that a part of it comes in the first line and another part on the next line.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each Test case should contain two positive integers, ‘N’ and ‘M’, where ‘N’ is the number of words and ‘M’ is the number of characters we require in each line. 

Following ‘N’ lines, contains one word each.

Output Format:

Each test case's only line of output should contain an integer denoting the minimum cost required to form the arrangement. 

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 300
1 <= |words[i]| <= 100
1 <= M <= 100

Time Limit: 1sec

Sample Input 1:

1
3 6
ab
a
b

Sample Output 1:

Explanation For Sample Input 1:

All the 3 words can be inserted in a single line.
ab a b Total Characters = 6
Hence extra spaces used are (6-6)^3=0

Sample Input 2:

1
4 5
a
bc
def
ghij

Sample Output 2:

Hint 1

Hint 2

Hint 3

Check every possible wrapping for every word and calculate the minimum cost.

Approaches (3)

Approach 1

Approach 2

Approach 3

Recursion Based Solution

Let' suppose we're at the ith word and jth line
Suppose we can put 5 words(total characters which are less than m) in the jth line(wi,wi+1......wi+4).
Now in this jth line, we will check all the different possibilities, for example, 1 word in the jth line, 2 words in a jth line and so on.
In each possibility, we will add the cost corresponding to the extra spaces in the jth line, i.e the number of total extra spaces we have to add to make a total of m characters.
Now we will take the optimal answer from the different possibilities we have i.e inserting only 1 word, 2 words...and so on in this jth line.

Time Complexity

O(N ^ N), where N is the number of words.

In the worst-case scenario, we can place N-words in a single line. Hence, for N lines, the overall Time Complexity becomes O(N ^ N).

Space Complexity

O(N), where N is the number of words.

The space required for an array of lengths of N words is O(N). Hence, the overall Space Complexity is O(N).

(100% EXP penalty)

Word Wrap

Console