Given an array, words[] of length n and an integer k.
The array contains the lengths of a series of words, while k represents the maximum length of a line (the number of characters that can be put into one line).
Assume that the length of each word is shorter than the line width.
The task is to put line breaks in the given sequence such that the lines are printed neatly.
When line breaks are inserted, there is a possibility that unoccupied spaces are left in each line. The unoccupied spaces include spaces put at the ends of every line except the last one.
The task is to minimise the total cost, where total cost = sum of all line costs, and each line cost equals (number of extra spaces in the line)^2.
Input: words = {3,2,2,5}, k = 6"
Output: 10
Input: words = {3,2,2}, k = 4
Output: 5
Solutions
Method 1: Recursion turned Memoization
The problem can be solved using a recursive (choose or not choose) approach.
The idea is to traverse the array from left to right, checking each time if the current word fits into the available space. (If it is not the first word on that line, it will take +1 extra space for white space.)
If the word can not fit into the current line, then we don't have a choice and need to keep the remaining space unoccupied. In this case, the cost of the remaining spaces will be added, and the current word will occupy space in a new line.
If the word can fit into the current line, then we have two choices:
1) Include the word in the current line - the word will occupy space in the current line with no cost yet.
2) Don't include the word in the current line - cost for current line unoccupied space will be added, a new line will start, and the word will take space in the next line.
Calculate and return the minimum of the above two options.
Complexity
The time complexity of this solution is O(n*k) and space complexity is O(n*k).