Text Justification - Solution & Explanation

Problem Overview: Given an array of words and a maximum line width, format the text so every line has exactly maxWidth characters. Words must stay in order, and extra spaces are distributed between words so the line becomes fully justified. The last line is left‑justified.

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

The most practical solution processes words line by line using a greedy strategy. Iterate through the input and keep adding words to the current line while the total length plus required spaces does not exceed maxWidth. Once the next word would overflow the line, finalize the current line by distributing spaces between its words. Compute the total remaining spaces and spread them evenly across the gaps; the first gaps receive one extra space when the division is uneven. If the line has a single word, pad spaces to the right. For the final line, join words with a single space and pad the remaining characters at the end. This approach scans each word once and performs constant work per line, giving O(n) time where n is the number of words (or total characters processed). Only a few counters and temporary variables are used, so the extra space is O(1) excluding the output. The logic mainly involves sequential processing of arrays and strings, which fits well with problems under Array and String.

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

A more theoretical approach treats the task like classic text formatting. Use dynamic programming to evaluate every possible break point between words and choose the configuration that minimizes uneven spacing or raggedness. Precompute line lengths for word ranges, then define dp[i] as the minimum penalty for formatting words starting at index i. Try placing words i..j on the same line, calculate the cost for unused spaces, and combine it with dp[j+1]. This explores many candidate layouts and guarantees an optimal formatting score under the chosen penalty rule. However, evaluating all word pairs leads to O(n²) time and memory. It’s rarely required for this specific problem because the platform’s rules already define exact spacing behavior rather than minimizing raggedness.

Recommended for interviews: Interviewers expect the greedy line construction approach. It directly simulates the formatting process and demonstrates strong control over indexing, spacing math, and edge cases like single‑word lines or the final line. The DP approach shows deeper understanding of text layout algorithms but is usually unnecessary overhead for this problem. From a patterns perspective, the greedy method is a clean example of Simulation combined with string manipulation.