We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Text Justification

Difficulty: Hard

Problem Description

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. Extra spaces between words should be distributed as evenly as possible. For the last line of text, it should be left-justified, and no extra space is inserted between words.

Key Insights

  • Each line must contain a combination of words that does not exceed maxWidth.
  • Extra spaces must be distributed evenly between words, with leftmost spaces getting priority if they cannot be evenly distributed.
  • The last line of the text should be left-justified with no extra spaces between words.
  • A greedy approach is effective, as we will fill each line with as many words as possible before moving to the next line.

Space and Time Complexity

Time Complexity: O(n) where n is the number of words, as we iterate through the list of words to form lines.
Space Complexity: O(m) where m is the total number of characters in the output, as we store the justified lines.

Solution

To solve the problem, we will use a greedy algorithmic approach. We will iterate through the list of words and form lines with words until adding another word would exceed the maxWidth. For each line, we will calculate the number of spaces needed to justify the text and distribute them between the words. We will handle the last line separately to ensure it is left-justified.

We'll use a list to collect the words for the current line and another list to store the final justified lines. The main steps are:

  1. Initialize a list for the current line and a variable to track the current line length.
  2. For each word, check if adding it to the current line would exceed maxWidth. If it does, justify the current line and reset for the next line.
  3. For the current line, calculate the total number of spaces needed and distribute them evenly among the words.
  4. Handle the last line by joining the words with a single space and padding with spaces to the right until maxWidth is reached.

Code Solutions

def fullJustify(words, maxWidth):
    res, current, num_of_letters = [], [], 0

    for word in words:
        if num_of_letters + len(word) + len(current) > maxWidth:
            for i in range(maxWidth - num_of_letters):
                current[i % (len(current) - 1 or 1)] += ' '  # Distribute spaces
            res.append(''.join(current))
            current, num_of_letters = [], 0
        current.append(word)
        num_of_letters += len(word)

    res.append(' '.join(current).ljust(maxWidth))  # Last line
    return res
← Back to All Questions