Word Wrap Problem

Difficulty Level Hard
Frequently asked in Arcesium Factset GreyOrange Microsoft Myntra Ola Cabs PayU
Dynamic ProgrammingViews 3133

Problem Statement

The word wrap problem states that given a sequence of words as input, we need to find the number of words that can be fitted in a single line at a time. So, for doing this we put breaks in the given sequence such that the printed document looks nice. The word editors such as Microsoft Office, Libre Office, and other document tools use line breaks to make the document look nice. Here, by nice we mean we place spaces in an evenly spread manner. There should not be lines with many extra spaces and some with small amounts.

Here, we also assume that our word length does not exceed the line size. Just to make things a bit more generic we are considering a const function in the question as (Number of extra space)^3, else it would have been too easy. This cost function may vary as per the question asked.

Word Wrap Dp approach

Example

Here, we will provide number of words, word size, and line size as input.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

Explanation: We can place 1st word on 1st line with 3 extra space, 2nd and 3rd word on 2nd line with 1 extra space, and the last word on 3rd line with no extra space (we won’t consider the spaces after the last word as extra spaces). Thus, using our cost function we find cost as 28.

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10
00

Explanation: Here we can place all words on the same line i.e. 1st line and thus cost = 0.

 

Approach for word wrap problem

The first approach which comes to mind is a greedy solution where we simply keep on placing the words in a single line. When we cannot place a word on the same line, we move to the second line. This seems to work just fine, but there’s a catch. This algorithm will not produce the optimal result because there may be cases such that if we change the extra spaces we may end up with a better global solution.

Output using Greedy Approach

”cat is an animal”, line size = 6
65

 

Just for simple understanding, we have shown the input as words instead of wordSize.

Explanation: cat is_

                        an____

                        animal

Here, there are 4 extra spaces on the second line and 1 on the third line.

Calculation: 4^3+1^3 = 65

 

There exists a better solution,

cat___

is an_

animal

Giving us a total cost of 28 (3^3 + 1^3  + 0^3), which is better than 65.

Now, we will solve the word wrap problem using Dynamic Programming. We know that our problem needs a global optimum solution and our previous algorithm was trying to give us local optimum as a result. Here we will find the extra space taken in each line, and will thus find the cost for each row respectively. We will maintain a matrix extraSpace which will tell the extraSpace left in a line, of words from i to j are laced on a single line. Then further we will use this extraSpace matrix to find the minimum cost.

Code

C++ Code for word wrap problem

#include <bits/stdc++.h>
using namespace std;

int wordWrap (int wordSize[], int n, int lineSize) 
{ 
  int extraSpace[n+1][n+1];
  int minCost[n+1];

  for (int i=1;i<=n;i++) 
  { 
    extraSpace[i][i] = lineSize - wordSize[i-1];
    for (int j=i+1;j<=n;j++) 
        extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
  }
  
  minCost[0] = 0; 
  for (int i = 1; i <= n; i++) 
  { 
    minCost[i] = INT_MAX;
    for (int j = 1; j <= i; j++) 
    { 
        int cost; // stores cost of storing words[i,j] in single line
        
        //if extraSpace required is negative, then we can't place
        //words[i,j] in a single line, else if we placed our last
        //word, then we don't consider extraSpace, else calculate
        //cost as per given cost function.
        if(extraSpace[j][i]<0)cost = INT_MAX;
        else if(i==n && extraSpace[j][i]>=0)cost = 0;
        else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
        
      if (minCost[j-1] != INT_MAX && cost != INT_MAX
      && (minCost[j-1] + cost < minCost[i])) 
        minCost[i] = minCost[j-1] + cost;
    }
  }
  
  return minCost[n];
} 

int main() 
{
    int t;cin>>t;
    while(t--) {
       int n;cin>>n;
       int wordSize[n];
       for(int i=0;i<n;i++)
            cin>>wordSize[i];
       int lineSize;cin>>lineSize;
       int ans = wordWrap(wordSize, n, lineSize);
       cout<<ans<<endl;
    }
}
3
4
3 2 2 6
6
3
1 1 1
10
4
1 1 1 1
5
28
0
0

Java Code for word wrap problem

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{ 
  static int wordWrap (int wordSize[], int n, int lineSize) 
  { 
    int extraSpace[][] = new int[n+1][n+1]; 
    int minCost[] = new int[n+1];
  
    for (int i=1;i<=n;i++) 
    { 
      extraSpace[i][i] = lineSize - wordSize[i-1];
      for (int j=i+1;j<=n;j++) 
          extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
    } 
    
    	minCost[0] = 0; 
    	for (int i = 1; i <= n; i++) 
    	{ 
    		minCost[i] = Integer.MAX_VALUE;
    		for (int j = 1; j <= i; j++) 
    		{ 
    		    int cost; // stores cost of storing words[i,j] in single line
    		    
    		    //if extraSpace required is negative, then we can't place
    		    //words[i,j] in a single line, else if we placed our last
    		    //word, then we don't consider extraSpace, else calculate
    		    //cost as per given cost function.
    		    if(extraSpace[j][i]<0)cost = Integer.MAX_VALUE;
    		    else if(i==n && extraSpace[j][i]>=0)cost = 0;
    		    else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
    		    
    			if (minCost[j-1] != Integer.MAX_VALUE && cost != Integer.MAX_VALUE
    			&& (minCost[j-1] + cost < minCost[i])) 
    				minCost[i] = minCost[j-1] + cost;
    		}
    	}
  
    return minCost[n];
  } 

  public static void main(String args[]) 
  {
      Scanner sc = new Scanner(System.in);
      
      int t = sc.nextInt();
      while(t-- > 0) {
         int n = sc.nextInt();
         int wordSize[] = new int[n];
         for(int i=0;i<n;i++)
              wordSize[i] = sc.nextInt();
         
         int lineSize = sc.nextInt();
         int ans = wordWrap(wordSize, n, lineSize);
         System.out.println(ans);
      }
  }
} 

 

3 
4 
3 2 2 6
6 
3 
1 1 1 
10 
4 
1 1 1 1 
5 
28 
0 
0

Complexity Analysis

Time Complexity: O(n^2)

Here, since our outer loop runs from 1 to n and our inner loop runs from 1 to i, we have a polynomial time complexity of O(n^2).

Space Complexity: O(n^2)

Here, our extraSpace array is a 2D array which is of size N*N, which gives us polynomial space complexity of O(N^2).

Translate »