Arrays - Text Justification

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Return the earliest hour at which the shop must be closed to incur a minimum penalty.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:

          [
            "This    is    an",
            "example  of text",
            "justification.  "
          ]

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:

        [
          "What   must   be",
          "acknowledgment  ",
          "shall be        "
        ]

Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word.

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is", "everything","else","we","do"], maxWidth = 20
Output:

        [
          "Science  is  what we",
          "understand      well",
          "enough to explain to",
          "a  computer.  Art is",
          "everything  else  we",
          "do                  "
        ]

Constraints:

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100
words[i].length <= maxWidth

Solution 1 - Loop through words array, and when maxLength is reached including spaces, apply spaces and add to result

In this approach, we will loop through the input array of words, and when the maxLength is reached, that is after applying minimum number of spaces between words, for example if there are three words ["cs", "code", "io"], that means we have to include two spaces between 3 words "cs code io" and there are no leading spaces, and trailing spaces except if it is a single word, or the last line (both must be left justified), then add the spaces between the words as per the rules and add it to result.

Implementation steps:

Create a variable result as List<String> to hold the final list of strings, and two more variables currentLine as List<String> to track current list of strings that we are reading, but not yet processed, currentLength to track the length of strings that we are currently reading.
Then, loop through each word from words array, and check if the currentLength (total length of words that we read so far) + currentLine size (number of words so far) + new word's length that we are currently looking at, if this is greater than maxLength, that means with the words collected so far are enough to fit into the maxLength with text justification.
- Now, find total number of spaces that it can accommodate between the words collected so far. totalSpaces = maxLength - currentLength;
- Then, check how many of these total spaces can be distributed equally among the lsit of words seen so far, if there are m spaces and n words, that means we have to distribute between n-1 words. So, we can get the distribution of spaces by dividing m with n-1, but if there is only one word in the list, then it will lead to divide by zero error, so to avoid that we can divide m with Math.max(1 , n-1). spacesDistro = totalSpaces / Math.max(1, currentLine.size() -1);
- After distributing the total spaces equally between the currentLine words, there still may be some spaces left, for example if there are 3 words and 5 spaces, then there will be one space left after distributing two spaces between the words, and we need to distribute these in a greedy fashion starting from left. To get how many such spaces by using modular operation on the same formula as above. remainingSpaces = totalSpaces % Math.max(1, currentLine.size() -1);
- Now, append the spacesDistro number of spaces between for each word in currentLine words, if there are more than one word, but if there is only one word, then append at the end of that word, then also append remainingSpaces starting from first word in the currentLine words.
- Once the currentLine of words are justified, then add this to result, and reset currentLine and currentLength for next iteration of words.
If the maxLength condition is not met, then simply add the current word to currentLine list of words, and increment currentLength by the current word length.
At the end, we will still be left with the last line, and last line is left justified, we will add one space between words and add all remaining spaces at the end, and add this to the result.

import java.util.ArrayList; import java.util.List; public class TextJustification { static List<String> fullJustify(String[] words, int maxWidth) { List<String> result = new ArrayList<>(); List<StringBuilder> currentLine = new ArrayList<>(); int currentLength = 0; for(String word : words) { if(currentLength + (currentLine.size()) + word.length() > maxWidth) { int totalSpaces = maxWidth - currentLength; // total spaces available int spacesDistro = totalSpaces / Math.max(1, currentLine.size() -1); // Math.max is to avoid divide by zero int remainingSpaces = totalSpaces % Math.max(1, currentLine.size() -1); // now add spaces at the end of strings for(int i=0; i<Math.max(1, currentLine.size()-1); i++) { // we don't need spaces for last word, but if there is only one word we need to StringBuilder sb = currentLine.get(i); for(int j=0; j<spacesDistro; j++) { // add required number of spaces sb.append(" "); } // + add remainingSpaces in greedy fashion if(remainingSpaces > 0) { sb.append( " "); remainingSpaces --; } } String justifiedLine = String.join("",currentLine); result.add(justifiedLine); //reset below, once a line is justified currentLine.clear(); currentLength = 0; } currentLine.add(new StringBuilder(word)); currentLength+=word.length(); } // add the last line here, since it may not have entered into if condition above if(!currentLine.isEmpty()) { String lastLine = String.join(" ", currentLine); int remainingSpaces = maxWidth - lastLine.length(); result.add(lastLine + (" ".repeat(remainingSpaces))); } return result; } public static void main(String[] args) { System.out.println(fullJustify(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16)); System.out.println(fullJustify(new String[]{"What","must","be","acknowledgment","shall","be"}, 16)); System.out.println(fullJustify(new String[]{"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"}, 20)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of words array.
Space complexity: O(n) for the result list.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: