Text Justification | LeetCode | InterviewBit | Solution Explained

Text Justification LeetCode/Justified Text InterviewBit is a interesting problem. I use raw logic to explain the solution in detail. Problem Links: LeetCode 68. Text Justification InterviewBit Justified Text.

0. Text Justification: Problem Discussion

0.0. IO Format

• inputs: words (a list of words), maxWidth (max width of a sentence)
• output: list of strings of each maxWidth length
• constraints:
  • pack as many words in the line as possible
  • add spaces to evenly space out the words
  • number of spaces must be the same between words
  • (add remaining spaces to the left) #left_spaces >= #right_spaces
  • last row is left justified

0.1. Example

The constraints are a bit tricky to understand, so let’s take an example.

The answer in this case is given as such:

• We see that we can efficiently pack “this” “is” and “an” in the first row, but we can’t fit “example”, even with 1 spacing. So, we just have the first 3 words and space them out equally.
• Since “example” was sent to the second row, we start with that. We are able to add “of” and “text” too, but not “justification”. We then add the appropriate spaces between. Since there are 3 total spaces, we give left space one more than right.
• finally, last row is simply left justified.

1. Text Justification: Observations & Logic

1.0. Intuitions

This question is amazing. It only requires basic knowledge of how strings work, and the rest is implementation. We can start following the rules and you’ll be amazed at how simple the answer is.

1.1. Observations

We can only decide the amount of spaces once we have decided what words to put in a row.

part 1: find the right number of words

1. find what all words we can pack in a row. assume minimal space of 1 for now.
2. generate an intermediate list of all such rows, containing the correct amount of words

part 2: find the right number of spaces

1. find the number of spaces required (maxWidth - sum(len(word) for word in row))
2. distribute the spacers in (almost) equal amounts to the spaces/(len(row)-1)
3. last line just gets one space between words, and remaining length of maxWidth is spaces.

2. Text Justification: Implementation

2.0. Code

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        # get the words, ensuing min rows consumed (greedily)
        rows = [""]
        for word in words:
            # if emplty row, add item by default
            if not rows[-1]: rows[-1] += word
            # if can add one more word, do so
            elif len(rows[-1]) + 1 + len(word) <= maxWidth: rows[-1] += " " + word
            # else, create a new row
            else: rows.append(word)
        
        # get a list of words instead (spaces dont matter right now)
        word_rows = [row.split() for row in rows]
        
        spaced_rows = []
        # fix the spaces
        for row in word_rows[:-1]:
            spaces = maxWidth - sum(len(word) for word in row)
            
            # if only one word, life is easy
            if len(row) == 1:
                spaced_rows.append(row[0] + " "*spaces)
            # for multiple words,
            else:
                # get the divisor and remainder
                # think why we use len(row)-1 :0
                d, r = divmod(spaces, len(row)-1)
                temp = ""

                for word in row:
                    # if some extra spaced remaining, consume them
                    if r: 
                        temp += word + " "*(d + 1)
                        r -= 1
                    else:
                        temp += word + " "*d
                # remove the last couple of spaces
                spaced_rows.append(temp.strip())
        
        # the last row has single spaced words
        spaced_rows.append(" ".join(word_rows[-1]))
        # dummy number of spaces to fill up till maxWidth
        spaced_rows[-1] += " "*(maxWidth - len(spaced_rows[-1]))
        return spaced_rows

2.1. Complexity Analysis

• Time: O(len(words) * maxWidth + len(rows) * maxWidth) for the part 1 and part 2 respectively
• Space: O(len(rows) + len(word_rows) + len(spaced_rows)) = O(len(rows)).

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.