68. Text Justificator

Text Justification

A decent way to have experience with queues.

Given a list of words, we pack as many consecutive words as possible into each line,

but each line must be padded to exactly maxWidth characters,

and spaces must be placed between words — how many depends on situations.

First In First Out

Set up a queue to hold words which are currently being assembled into a line.

Since at least one space is needed between any two adjacent words, minimum line length formed by these queued words is:

$L = \text{len}(\text{queue}) - 1 + \Sigma_i \; \text{len}(\text{word}_i)$

Case 1: Length Exceeded

Once the current word $word_j$ causes

$L + 1 + \text{len}(word_j) > \text{maxWidth}$,

it's time for all queued words to form a line.

After forming a line, queue clears, and $word_j$ enters queue as next line's head word.

Case 2: Space Remains

Otherwise, simply add $word_j$ to queue. The line doesn't need to form yet.

Forming Line

As mentioned, number of spaces between adjacent words depends on situations.

The problem specifies two spacing styles.

1. Left Justification

If the line being formed is the last line, it should be left-justified:

exactly one space between adjacent words.

If total length still hasn't reached maxWidth after filling, pad spaces to the end of the line.

Note: if a non-last line contains only one word, the spacing behavior automatically becomes left-justified.

2. Right Justification

Lines that are not the last line and contain at least two words use right justification.

We have $\text{len}(\text{queue}) - 1$ gaps between words.

Total spaces to distribute: $S = \text{maxWidth} - \Sigma_i \; \text{len}(\text{word}_i)$

Each gap first receives: $\lfloor S \div (\text{len}(\text{queue}) - 1) \rfloor$ spaces

Remainder $M = S \bmod{(\text{len}(\text{queue}) - 1)}$ is usually greater than zero, meaning $M$ extra spaces still need to be dealt.

Very simple: take the leftmost $M$ gaps and give each one an extra space.

Grasp both justification styles, and this problem is all done.

C++

#include <deque>
#include <string>
#include <vector>
using namespace std;

class TextJustificator // LeetCode Q.68.
{
private:
    deque<string> queue;

    string formSentence(int charsCount, int maxWidth, bool leftJustify) {
        string intervalSpaces = "";
        int intervalsCount = queue.size() - 1, modulo = 0;

        if (intervalsCount > 0 && !leftJustify) {
            int quotient = (maxWidth - charsCount) / intervalsCount;
            for (int num = 0; num < quotient; num++)
                intervalSpaces += " ";

            modulo = (maxWidth - charsCount) % intervalsCount;
        }

        string sentence = "";

        for (int idx = 0; idx < queue.size(); idx++) {
            sentence += queue[idx];

            if (idx < queue.size() - 1) // Not the last word.
            {
                if (leftJustify) {
                    sentence += " "; // Left-justification.
                    continue;
                }

                sentence += intervalSpaces; // Right-justification.
                if (modulo > idx)
                    sentence += " "; // Need to pad extra space at left intervals.
            }
        }
        queue.clear(); // Reset for future usage.

        // Right end padding only runs for left-justification.
        while (sentence.size() < maxWidth)
            sentence += " ";
        return sentence;
    }

public:
    vector<string> justifyText(vector<string>& words, int maxWidth) {
        vector<string> justifiedSentences;
        int charsCount = 0; // Characters only. Not counting interval spaces.

        for (const auto& word : words) {
            // Current sentence is finalized.
            if (charsCount + queue.size() - 1 + word.size() + 1 > maxWidth) {
                string sentence = formSentence(charsCount, maxWidth, false);
                justifiedSentences.push_back(sentence);
                charsCount -= charsCount; // Reset for the next sentence.
            }

            queue.push_back(word);
            charsCount += word.size();
        }

        // Deal with last sentence. Last sentence must be left-justified.
        string sentence = formSentence(charsCount, maxWidth, true);
        justifiedSentences.push_back(sentence);
        return justifiedSentences;
    }
};

Python

class TextJustificator:  # LeetCode Q.68.
    def __init__(self) -> None:
        self.queue: list[str] = []

    def _form_sentence(self, chars_count: int, max_width: int, left_justify: bool) -> str:
        interval_spaces = ""
        intervals_count = len(self.queue) - 1
        modulo = 0

        if intervals_count > 0 and not left_justify:
            quotient = (max_width - chars_count) // intervals_count
            interval_spaces += " " * quotient

            modulo = (max_width - chars_count) % intervals_count

        sentence = ""

        for idx, word in enumerate(self.queue):
            sentence += word

            if idx < len(self.queue) - 1:  # Not the last word.
                if left_justify:
                    sentence += " "  # Left-justification.
                    continue

                sentence += interval_spaces  # Right-justification.
                if modulo > idx:
                    sentence += " "  # Need to pad extra space at left intervals.

        self.queue.clear()  # Reset for future usage.

        # Right end padding only runs for left-justification.
        return sentence + " " * (max_width - len(sentence))

    def justify_text(self, words: list[str], max_width: int) -> list[str]:
        self.queue = []

        justified_sentences: list[str] = []
        chars_count = 0  # Characters only. Not counting interval spaces.

        for word in words:
            # Current sentence is finalized.
            if chars_count + len(self.queue) - 1 + len(word) + 1 > max_width:
                sentence = self._form_sentence(chars_count, max_width, False)
                justified_sentences.append(sentence)
                chars_count -= chars_count  # Reset for the next sentence.

            self.queue.append(word)
            chars_count += len(word)

        # Deal with last sentence. Last sentence must be left-justified.
        sentence = self._form_sentence(chars_count, max_width, True)
        justified_sentences.append(sentence)
        return justified_sentences

Both time and space complexity are $O(n)$.