Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Solution: Text Justification

Explore the greedy technique for solving text justification challenges by constructing lines with maxWidth by packing as many words as possible. Understand how to distribute spaces evenly for fully justified lines and handle special cases like the last line or single-word lines. This lesson guides you through implementing the solution efficiently, focusing on algorithmic optimization and formatting rules to master this common coding interview pattern.

We'll cover the following...

Statement

You are given an array of strings, words, and an integer, maxWidth. Your task is to reformat the text by arranging the words into lines of a specified width. Each line must have exactly maxWidth characters.

Words should be packed into lines using a greedy approach, which means you should fit as many words as possible onto each line before moving to the next. For this purpose, if the length of the words is less than the maxWidth, then add empty spaces ‘ ’ to adjust the length of each line.

The formatting rules are as follows:

  • For all lines except the last one, distribute extra spaces between words as evenly as possible to align both left and right.

  • If the spaces don’t divide evenly, the leftmost gaps should receive the extra spaces ‘ ’.

  • The last line of text and any line with only a single word must be left-justified. This means words are separated by a single space separates words, and the remaining width is filled with spaces on the right.

You can assume the following:

  • A word is defined as a character sequence consisting of non-space characters only.

  • Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.

  • The input array words contains at least one word.

Constraints:

  • 1≤1 \leq words.length ...