Vultr DocsLatest Content

Text Justification

Updated on 26 June, 2025
Text Justification header image

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

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp 
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;
    }
};

Implement text justification using C++ to format words into a justified text with a specified maximum width. To achieve this:

  • Create a TextFormatter class containing methods to justify text and manage internals of building and formatting lines.
  • Use the justifyText method within the TextFormatter class. It initializes storing results and iterates through words to gather and build lines until all words are processed.
  • Employ two helper methods: gatherWords to collect words that fit within the maximum width constraint and buildLine to format and distribute spaces among collected words fittingly.
  • In buildLine, calculate the total length of words and distribute spaces. If there is only one word or it's the last line, left-justify by adding trailing spaces. Otherwise, distribute spaces evenly between words, adding extra spaces to the first few words if spaces cannot be evenly divided.
  • joinString consolidates words into a string with spaces or extra spaces if applicable.
  • Gather formatted lines into a vector of strings representing the justified text, which the justifyText method ultimately returns.

Ensure all edge cases, such as single-word lines or the last line of the text, are handled to meet the requirements of text justification as traditionally understood in typesetting.

java 
class TextFormatter {
    public List<String> justifyText(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int currentIndex = 0;

        while (currentIndex < words.length) {
            List<String> lineWords = gatherWords(currentIndex, words, maxWidth);
            currentIndex += lineWords.size();
            result.add(formatLine(lineWords, currentIndex, words, maxWidth));
        }

        return result;
    }

    private List<String> gatherWords(int start, String[] words, int maxWidth) {
        List<String> line = new ArrayList<>();
        int lineLength = 0;

        while (start < words.length && lineLength + words[start].length() <= maxWidth) {
            line.add(words[start]);
            lineLength += words[start].length() + 1;
            start++;
        }

        return line;
    }

    private String formatLine(
        List<String> currentLine,
        int currentIndex,
        String[] words,
        int maxWidth
    ) {
        int lineLength = -1;
        for (String word : currentLine) {
            lineLength += word.length() + 1;
        }

        int remainingSpace = maxWidth - lineLength;

        if (currentLine.size() == 1 || currentIndex == words.length) {
            return String.join(" ", currentLine) + " ".repeat(remainingSpace);
        }

        int spaceBetweenWords = remainingSpace / (currentLine.size() - 1);
        int additionalSpace = remainingSpace % (currentLine.size() - 1);

        for (int j = 0; j < additionalSpace; j++) {
            currentLine.set(j, currentLine.get(j) + " ");
        }

        for (int j = 0; j < currentLine.size() - 1; j++) {
            currentLine.set(j, currentLine.get(j) + " ".repeat(spaceBetweenWords));
        }

        return String.join(" ", currentLine);
    }
}

The provided Java solution demonstrates a method for performing text justification, ensuring each line of text fits within a specified maximum width while maintaining even spacing between words. The solution is encapsulated in the TextFormatter class which contains a method justifyText that takes an array of words and an integer for the maximum width as parameters.

  • The justifyText method iterates over the input words and constructs each line to not exceed the maxWidth, utilizing subordinate methods for gathering words into a line and formatting the line:

    1. During each iteration, gatherWords is called to select as many words as can fit into the current line given the maxWidth.
    2. formatLine is subsequently invoked to properly space the words in the line, considering scenarios where the line might contain only a single word or it's the last line of text.

  • gatherWords achieves its functionality by adding words to the current line until the addition of another word would exceed maxWidth. It ensures a basic space is considered for each word added.

  • formatLine applies the necessary spacing:

    1. Calculates the total length of words in the line and the remaining space that needs to be filled with white spaces.
    2. If the line contains a single word or it's the last line, it joins the words with a single space and appends the remaining spaces at the end.
    3. For other lines, it distributes extra spaces evenly and adds any remainder to the initial words in the list.

By iterating through all words and correctly appending and formatting words for each line, the justifyText method effectively compiles a list of justified text lines that conform to the specified width. The solution employs string manipulation and list operations to maintain readability and efficiency.

c 
struct line_content {
    char** segments;
    int count;
};

struct line_content extractSegments(int index, char** phrases, int totalPhrases, int maxWidth) {
    struct line_content line;
    line.segments = (char**)malloc(totalPhrases * sizeof(char*));
    line.count = 0;
    int lineLength = 0;
    while (index < totalPhrases && lineLength + strlen(phrases[index]) <= maxWidth) {
        line.segments[line.count++] = phrases[index];
        lineLength += strlen(phrases[index]) + 1;
        index++;
    }
    return line;
}

char* concatenate(struct line_content parcel, char* spacer) {
    if (parcel.count == 0) {
        return "";
    }
    int fullLength = strlen(spacer) * (parcel.count - 1);
    for (int i = 0; i < parcel.count; i++) {
        fullLength += strlen(parcel.segments[i]);
    }
    char* result = (char*)malloc((fullLength + 1) * sizeof(char));
    strcpy(result, parcel.segments[0]);
    for (int i = 1; i < parcel.count; i++) {
        strcat(result, spacer);
        strcat(result, parcel.segments[i]);
    }
    return result;
}

char* formatLine(struct line_content segment, int currentWord, int totalWords, int maxWidth) {
    int baseLen = -1;
    for (int i = 0; i < segment.count; i++) {
        baseLen += strlen(segment.segments[i]) + 1;
    }
    int spacesNeeded = maxWidth - baseLen;
    if (segment.count == 1 || currentWord == totalWords) {
        char* formatted = (char*)malloc((maxWidth + 1) * sizeof(char));
        strcpy(formatted, concatenate(segment, " "));
        for (int i = strlen(formatted); i < maxWidth; i++) formatted[i] = ' ';
        formatted[maxWidth] = '\0';
        return formatted;
    }
    int dividerCount = segment.count - 1;
    int spacesBetween = spacesNeeded / dividerCount;
    int extraSpacesCount = spacesNeeded % dividerCount;
    for (int k = 0; k < extraSpacesCount; k++) {
        segment.segments[k] =
            realloc(segment.segments[k], (strlen(segment.segments[k]) + 1 + 1) * sizeof(char));
        strcat(segment.segments[k], " ");
    }
    for (int k = 0; k < dividerCount; k++) {
        segment.segments[k] =
            realloc(segment.segments[k],
                    (strlen(segment.segments[k]) + 1 + spacesBetween) * sizeof(char));
        char spaceBuffer[spacesBetween + 1];
        memset(spaceBuffer, ' ', spacesBetween);
        spaceBuffer[spacesBetween] = '\0';
        strcat(segment.segments[k], spaceBuffer);
    }
    return concatenate(segment, " ");
}

char** justifyText(char** phrases, int totalPhrases, int maxWidth, int* linesCount) {
    char** justifiedText = (char**)malloc(totalPhrases * sizeof(char*));
    *linesCount = 0;
    int index = 0;
    while (index < totalPhrases) {
        struct line_content lineSegment = extractSegments(index, phrases, totalPhrases, maxWidth);
        index += lineSegment.count;
        justifiedText[*linesCount] = formatLine(lineSegment, index, totalPhrases, maxWidth);
        (*linesCount)++;
    }
    return justifiedText;
}

The provided C code handles the text justification problem, where the goal is to distribute words across a specified width with appropriate spacing. The code breaks down the functionality into several functions, each handling specific aspects of the text justification process. Here is a breakdown of the key components:

  • struct line_content

    • This structure holds an array of strings (segments) and a count of these segments.

  • extractSegments function

    • This function processes input phrases and forms a line ensuring it does not exceed the maximum width. It returns a line_content structure containing the selected segments and their count.

  • concatenate function

    • Given a line_content object and a spacer (string used to separate words), it concatenates the segments into a single string, inserting the spacer between each word. This is useful for both constructing a fully justified line and creating the final formatted string.

  • formatLine function

    • It formats a line to meet the requirement of text justification. If the line is the last line in the text or contains only one word, spaces are added at the end. Otherwise, spaces are distributed evenly amongst words. This function dynamically adjusts memory allocation for each segment to accommodate extra spaces.

  • justifyText function

    • This is the main function that orchestrates the text justification by iterating over the input phrases. It uses extractSegments to get line segments and formatLine to format these segments. It tracks the number of lines generated and stores each justified line.

Usage Steps

  1. Define the maximum width (maxWidth), an array of strings (phrases), and its size (totalPhrases).
  2. Initialize an integer (linesCount) to keep count of the resultant lines after justification.
  3. Call justifyText passing the phrases, their count, the maxWidth, and the address of linesCount.
  4. Process the returned array of justified text lines.

Memory Management

  1. Memory management is carefully handled using malloc and realloc functions to allocate and adjust memory as needed.
  2. It is important to ensure that allocated memory is appropriately freed after use to avoid memory leaks.

The code effectively demonstrates managing string operations, memory allocation, and algorithmic logic to solve a complex real-world problem such as text justification in programming.

js 
var justifyText = function (wordsArray, maxWidth) {
    let result = [];
    let index = 0;
    while (index < wordsArray.length) {
        let lineWords = fetchWords(index, wordsArray, maxWidth);
        index += lineWords.length;
        result.push(formatLine(lineWords, index, wordsArray, maxWidth));
    }
    return result;

    function fetchWords(startIndex, words, lineMaxWidth) {
        let line = [];
        let lineLength = 0;
        while (startIndex < words.length && lineLength + words[startIndex].length <= lineMaxWidth) {
            line.push(words[startIndex]);
            lineLength += words[startIndex].length + 1; // add space
            startIndex++;
        }
        return line;
    }

    function formatLine(line, idx, wordList, maxWidth) {
        let totalLength = -1;
        line.forEach(word => {
            totalLength += word.length + 1; // add spaces
        });
        let additionalSpaces = maxWidth - totalLength;
        if (line.length === 1 || idx === wordList.length) {
            return line.join(" ") + " ".repeat(additionalSpaces);
        }
        let wordsInLine = line.length - 1;
        let evenSpace = Math.floor(additionalSpaces / wordsInLine);
        let additionalSpaceCount = additionalSpaces % wordsInLine;
        for (let j = 0; j < additionalSpaceCount; j++) {
            line[j] += " ";
        }
        for (let j = 0; j < wordsInLine; j++) {
            line[j] += " ".repeat(evenSpace);
        }
        return line.join(" ");
    }
};

In the given JavaScript solution, you are presented with a function justifyText designed to justify text within a given width constraint. The function achieves the task of text justification by ensuring each line of text fits exactly within the specified maxWidth, aligning spaces appropriately between words.

  • At the start, justifyText initializes an empty array result to collect the formatted lines and uses an index to track the current position in the input wordsArray.

  • The main process loops over wordsArray to collect and justify lines until all words are processed:

    1. It calls fetchWords to gather as many words as fit into maxWidth without breaking any word. Space between words is accounted for in the measure of line width.
    2. It then updates the index by adding the number of words collected for the current line.
    3. formatLine is invoked with the words to arrange them into a justified format where necessary spaces are added. The line is then added to the result array.

  • The helper function fetchWords:

    1. Starts with an empty array for the line and a counter for the line length.
    2. It iterates through words starting from a given index, adding words to the line if they fit when including a space for separation.
    3. Returns the line once the maxWidth is met or exceeds.

  • The formatLine function:

    1. First calculates the total length of all words plus the spaces in the line.
    2. Computes the number of additional spaces needed to make the line length equal to maxWidth.
    3. If the line is the last one or contains just one word, the spaces are added at the end of the line.
    4. For other lines, it calculates even distribution of spaces and allocates any extra spaces to the early words in the line.
    5. Each word (except the last one) is then extended by adding calculated spaces, thus justifying the text.

  • The function finally returns the result array containing all justified lines.

This function is efficient for creating a text block aligned both left and right by ensuring optimal distribution of spaces, conforming to the constraints of text justification. Remember, the solution works directly for arrays of words and specified maximum widths without requiring pre-formatting or additional handling of string inputs.

python 
class Solution:
    def justifyText(self, words: List[str], maxWidth: int) -> List[str]:
        def gather_words(index):
            line_content = []
            current_width = 0

            while index < len(words) and current_width + len(words[index]) <= maxWidth:
                line_content.append(words[index])
                current_width += len(words[index]) + 1
                index += 1

            return line_content

        def format_line(line_words, index):
            current_line_length = -1
            for word in line_words:
                current_line_length += len(word) + 1

            available_space = maxWidth - current_line_length

            if len(line_words) == 1 or index == len(words):
                return " ".join(line_words) + " " * available_space

            num_of_spaces = len(line_words) - 1
            even_space = available_space // num_of_spaces
            extra_space_count = available_space % num_of_spaces

            for j in range(extra_space_count):
                line_words[j] += " "

            for j in range(num_of_spaces):
                line_words[j] += " " * even_space

            return " ".join(line_words)

        justified_text = []
        current_index = 0

        while current_index < len(words):
            words_in_line = gather_words(current_index)
            current_index += len(words_in_line)
            justified_text.append(format_line(words_in_line, current_index))

        return justified_text

This Python3 solution involves creating a class Solution with a method justifyText that formats a list of words into a justified text layout. The function takes a list of words and a maxWidth, and orchestrates each line's width to match maxWidth precisely.

Key Functions:

  • gather_words(index): Collects words that can fit within maxWidth starting from a given index. It handles accumulation of words and ensures that they do not exceed the provided maxWidth.

  • format_line(line_words, index): Assembles a single line from the given words. It adjusts spaces between words to distribute them evenly across the line. If a single word exists in the line or it's the last line, spaces are added only at the end. For other cases, spaces are divided evenly with additional spaces added to earlier words if they do not divide cleanly.

Process Flow:

  1. Initialize an empty list justified_text to hold each formatted line.
  2. Use a while loop to iterate over words using an index current_index initially set to zero.
  3. Inside the loop, retrieve words fitting in a single line using gather_words.
  4. Adjust format and spacing of these words using format_line.
  5. Append the formatted line to justified_text and increment the index by the number of words just processed.
  6. Return the justified_text containing all formatted lines.

Output:

The output of the method is a list of strings, where each string represents a line of text justified to match the specified maxWidth. This allows for presentation of text in a visually cohesive manner, maintaining a clean, aligned look on both the left and right margins across multiple lines of text.

Comments

No comments yet.