Visa Paragraph Text Alignment Formatter (OA)

You are asked to build a text formatter that takes one or more paragraphs and emits lines no longer than a given width W, applying a specified alignment per paragraph (left, right, center, or justify). Words are never split; paragraphs remain separated by a single blank line. The main challenge is packing words into lines (word-wrapping) and then applying the alignment rules precisely, including distributing extra spaces for justified lines and handling the paragraph's final line as left-justified.

This question naturally splits into two stages: first, line breaking (a greedy packing or simulation that groups words into the longest possible line without exceeding W), and second, line rendering (apply left/right/center padding or distribute gaps for justify). You should process each paragraph independently: build lines from the paragraph's words, then format each line according to the paragraph's alignment label. For justify, treat every non-final line specially by distributing additional spaces across gaps from left to right.

You should demonstrate correctness and attention to edge cases: words equal to W, single-word lines, odd padding when centering (extra space goes to the left), and paragraphs with a single line (justify reduces to left). Discuss runtime and memory (linear in total text length) and show a clear greedy approach for packing plus deterministic space distribution for justify. Provide sample reasoning, consider simple test cases, and be ready to explain trade-offs between greedy and DP-based line-breaking strategies.