Text Justification - Video Solutions

Problem Overview: You receive a list of words and a maximum line width. The goal is to arrange the words so each line contains exactly maxWidth characters. Spaces must be distributed between words to fully justify the line, except the last line which is left‑justified.

This problem is mostly about careful string manipulation and spacing logic. You group words into lines, then calculate how many spaces must be inserted between them to reach the exact width. The tricky part is distributing spaces evenly and handling edge cases such as a single word line or the final line.

Approach 1: Greedy Line Construction (O(n) time, O(n) space)

The optimal solution processes words greedily. Iterate through the input and keep adding words to the current line while the total length plus required spaces stays within maxWidth. Once adding another word would exceed the limit, finalize the current line. Compute the remaining spaces and distribute them between word gaps. If multiple gaps exist, divide spaces evenly and place the extra spaces in the leftmost gaps. If the line has only one word, pad the rest with trailing spaces.

For the last line, apply left justification: join words with a single space and pad the remaining characters at the end. This approach works because each word is processed exactly once and each line is constructed immediately when it becomes full. The logic relies on simple iteration over the array of words and controlled spacing simulation.

This greedy strategy runs in O(n) time where n is the total number of characters across all words. Space complexity is O(n) for storing the resulting lines.

Approach 2: Dynamic Programming Approach (O(n²) time, O(n) space)

A dynamic programming solution treats text formatting as an optimization problem. Instead of greedily finalizing lines, consider every possible place a line could end. For each starting index, try placing words until the width limit is exceeded. Calculate a penalty score based on the unused spaces in that line. The DP state dp[i] stores the minimum penalty when formatting from word i to the end.

During reconstruction, choose the breakpoints that produced the minimum penalty and format each line accordingly. This approach resembles classic word wrap algorithms used in typesetting systems. It requires nested iteration over word ranges and explicit reconstruction of lines, which leads to O(n²) time complexity and O(n) extra space.

The DP strategy is useful when formatting rules change, such as minimizing raggedness instead of enforcing strict justification. It models the problem as a structured simulation of layout decisions.

Recommended for interviews: Interviewers expect the greedy line construction approach. It demonstrates strong control over string manipulation and edge case handling. The dynamic programming version shows deeper understanding of text layout problems but is rarely required unless the problem explicitly asks for optimal formatting.