Text Justification

Problem Statement

Given an array of strings named words and an integer maxWidth, the task is to format the text such that each line of output text has exactly maxWidth characters while being fully justified on both left and right margins. A text justification involves packing words into lines such that:

• You strive to fit as many words on a line as possible using a greedy approach.
• If a line is not the last line and is not made up of a single word, you pad spaces between words to ensure that each line is maxWidth characters long, distributing extra spaces as evenly as possible between words. If spaces can't be distributed equally, then the extra spaces are placed on the left-most gaps.
• The last line of the text should be left-justified with no extra space inserted between the words, and spaces are only added after the last word till it reaches maxWidth.
• Each line of the output should contain the words separated by at least a single space and should neither contain trailing nor leading spaces.

Examples

Example 1

Input:

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

Output:

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

Example 2

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.

Example 3

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

Approach and Intuition

To develop a solution for text justification as per the given requirements, the following approach can be used, inspired by the examples and constraints:

1. Initialization:

   • Start by creating an empty list called justified_text to store the result.
   • Initialize pointers or counters like current_length to track the length of the words in the current line including the minimal spaces (one space between each word).
   • Initialize a temporary list current_line to hold the words for the current line.

2. Building Lines:

   • Loop through each word in the words array.
   • For each word, determine if it can be added to the current_line without exceeding the maxWidth when combined with the minimal required spaces.
   • If it fits, add the word to current_line and adjust current_length.
   • If it doesn't fit, move to the step of justifying the current line.

3. Justifying a Line:

   • If the current_line is not the last line:
     • Calculate the total number of spaces needed to reach maxWidth.
     • Distribute these spaces between the words in current_line. If the spaces don't distribute evenly, place the extra spaces in the gaps starting from the left.
   • If the current_line is the last line:
     • Join the words with a single space and then pad additional spaces at the end until the line reaches maxWidth.

4. Adding to Result:

   • Once the line is justified, add it to the justified_text.
   • Reset current_line and current_length to start forming the next line.

5. Handling Edge Cases:

   • Single word lines: If a line consists of a single word, it should be followed by spaces until the line length reaches maxWidth.
   • Handle the case where all words are processed but the last line has not been added to the result due to the loop termination conditions.

Following these steps will ensure that each line adheres to the maxWidth constraint while also respecting the justification rules provided in the problem statement. Checking the examples, it reassures that the approach of padding and spacing distribution is appropriately planned to meet both the functionality and constraint requirements.

Solutions

class TextFormatter {
public:
    vector<string> justifyText(vector<string>& words, int maxWidth) {
        vector<string> formattedText;
        int index = 0;
        while (index < words.size()) {
            vector<string> lineWords = gatherWords(index, words, maxWidth);
            index += lineWords.size();
            formattedText.push_back(buildLine(lineWords, index, words, maxWidth));
        }
        return formattedText;
    }
    
private:
    vector<string> gatherWords(int idx, vector<string>& words, int maxWidth) {
        vector<string> line;
        int lineLength = 0;
        while (idx < words.size() && lineLength + words[idx].size() <= maxWidth) {
            line.push_back(words[idx]);
            lineLength += words[idx].size() + 1;
            idx++;
        }
        return line;
    }
    
    string buildLine(vector<string>& lineWords, int idx, vector<string>& words, int maxWidth) {
        int totalLength = -1;
        for (const string& word : lineWords) {
            totalLength += word.size() + 1;
        }
        int spaceLeft = maxWidth - totalLength;
        if (lineWords.size() == 1 || idx == words.size()) {
            string result = joinString(lineWords, " ");
            result += string(spaceLeft, ' ');
            return result;
        }
        int spaceCount = lineWords.size() - 1;
        int spacesPerWord = spaceLeft / spaceCount;
        int additionalSpaces = spaceLeft % spaceCount;
        for (int j = 0; j < additionalSpaces; j++) {
            lineWords[j] += " ";
        }
        for (int j = 0; j < spaceCount; j++) {
            lineWords[j] += string(spacesPerWord, ' ');
        }
        return joinString(lineWords, " ");
    }
    
    string joinString(vector<string>& lineWords, const string& delimiter) {
        if (lineWords.empty()) {
            return "";
        }
        string result(lineWords[0]);
        for (int i = 1; i < lineWords.size(); i++) {
            result += delimiter + lineWords[i];
        }
        return result;
    }
};