Word Wrap
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.

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

Question

Word Wrap

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.

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

Accepted Answer

I first used recursion and then converted it to a dynamic programming based solution.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n^n)Explanation:

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).

Accepted Answer

Dynamic Programming 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 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.
Now as it is clear from the above steps that we are calling the function recursively at each step, so the time complexity will now be exponential. Hence to reduce the time complexity, we will use the technique of memoization(Dynamic Programming).
From Observation, it can be clearly seen that there are overlapping subproblems.
Hence, we will make a 2-Dimensional array of size N^2 to maintain the states of the dp, here the statedp[i][j] represents the minimum cost of the ith word at the start of the jth line.
- We will be trying out all the possibilities and we know that with N-words, there can be at most N lines(only 1 word in each line). wordsLength is a vector of size N, containing lengths of N-words and maxLimit is the number of characters we want in each line.
- For calculating the minimum cost, we will make calculateCost() in which we will pass the following arguments -
  - Current word at which we are
  - Current line at which we are
  - Vector of lengths of words
  - The character required in each line
- We will check for different possibilities we can have at different values of i and j and make the optimal choice out of it.
- For example, if we can insert 4 words in line j starting from ith word i.e.(i,i+1,i+2,i+3) and we will check 4 different possibilities we can have in this line starting with the word i.
  - insert only one word in line j i.e.(ith word) and move to the next line.
  - insert only two words in line j i.e.(ith and (i+1)th word) and move to the next line.
  - insert only three words in line j i.e.(ith,(i+1)th and (i+2)th word) and move to the next line.
  - insert only four words in line j i.e.(ith,(i+1)th, (i+2)th and (i+3)th word) and move to the next line.
- The possibility that will give me the minimum cost, I will go for that.
- To make the solution run faster, we will use the technique of memoization i.e. we will not calculate the answers for the states we have already calculated earlier.
- For this, we will maintain a 2-D vector that will store the minimum cost for all combinations of i and j i.e. dp[i][j] = minimum cost to insert words starting from ith word and starting in the jth line.
- Now, along with the 4 arguments in the calculateCost() function, we will be passing also the DP vector so finally there will be 5 arguments for the optimised solution.
- Our answer will be equal to dp[0][0], i.e starting from the first word and the first line.

Space Complexity: O(n^2)Explanation:

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

The space required to create a 2-Dimensional Array is O(N ^ 2). Hence, the overall Space Complexity is O(N ^ 2).

Time Complexity: O(n^2)Explanation:

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

As we know that the upper limit for the words is N, and similarly the upper limit for the number of lines is also N, which means we can fill N-words in lines varying from 1 from N. Hence for covering all the possibilities of arranging these N-words in N lines will cost us N * N time. Hence, the overall Time Complexity is O(N ^ 2).

Accepted Answer

bottom Up Dynamic Programming

In This Approach, we will calculate the cost of all possible lines using dynamic programming and then calculate the final cost by taking the minimum from every possible line.

The steps are as follows:

Take a vector “len” in which we will store the length of every given string.
Take a 2D array “cost” to store the cost of every possible line which can be formed using the given lengths.
Now iterate through the array “len” from 0 to n-1(say iterator be i):
- If we are taking only one element in the current line then the cost[i][i] will be “m” - “len[i]”.
- Now iterate through the array from i+1 to n-1(say iterator be j):
  - Update the value of “cost[i][j]” such that ‘i’ denote the line number and j denote the number of elements in the current line.
  - “Cost[i][j]” will be cost[i][j - 1] - len[j] - 1.
Now iterate through the cost array again to update all the values which are less than 0 to be INT_MAX.
Else update the cost[i][j] to cost[i][j] ^ 3.
Take an array “mincost” of length n in which we will store the minimum cost of taking every element from the list.
Iterate through the array from n-1 to 0(say iterator to be i):
- Update mincost[i] = cost[i][n - 1] denoting that the minimum cost of making word wrap from current element to the final element is cost[i][n - 1].
- Now iterate through the array from n-1 to ‘i’(say iterator be j):
  - Check if the value of “mincost[i]” can be minimized using by changing the line at index ‘j’. If it can be minimised then update the value of “mincost[i]” = “cost[i][j - 1]” + “mincost[j]”.
Finally, return “mincost[0]”.

Space Complexity: O(n^2)Explanation:

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

The space required to create a 2-Dimensional Array is O(N ^ 2). Hence, the overall Space Complexity is O(N ^ 2).

Time Complexity: O(n^2)Explanation:

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

Since we are iterating through the array in a nested loop.

Hence the time complexity is O(N ^ 2).

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

Note:

Input Format:

Output Format:

Note :

Constraints:

Top Microsoft Corporation Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Microsoft Corporation Software Engineer