Format words into wrapped/justified lines
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of words (strings with no spaces) and an integer `maxWidth`.
Implement text formatting in two variants:
## Variant A — Basic word wrap (no padding)
Return lines by packing words **greedily** from left to right:
- Each line contains as many words as possible.
- Words in a line are separated by **a single space**.
- **Do not** pad the end of the line with extra spaces.
## Variant B — Full justification (fixed width)
Return lines of **exactly** `maxWidth` characters:
- Pack words greedily as in Variant A.
- For every line **except the last**:
- Distribute spaces between words so that the line length is exactly `maxWidth`.
- If the spaces do not divide evenly, the **leftmost gaps** get more spaces.
- If a line has only **one** word, left-justify it and pad trailing spaces to reach `maxWidth`.
- For the **last** line:
- Left-justify: words separated by a single space, then pad trailing spaces to reach `maxWidth`.
### Input
- `words: List[str]`
- `maxWidth: int`
### Output
- `List[str]` lines formatted according to the chosen variant.
### Constraints (typical)
- `1 <= len(words) <= 10^4`
- `1 <= len(words[i]) <= maxWidth`
- `1 <= maxWidth <= 100`
Quick Answer: This question evaluates practical programming skills in string processing, greedy packing, and careful handling of spacing and edge cases, and falls under the Coding & Algorithms domain.
Part 1: Greedy Word Wrap Without Padding
Given a list of words where each word contains no spaces, and an integer `maxWidth`, split the words into lines using greedy word wrap. Build each line from left to right, placing as many words as possible without making the line longer than `maxWidth`. Words in the same line must be separated by exactly one space. Do not add any trailing spaces to the end of a line. Return the list of produced lines. If the input list is empty, return an empty list.
Constraints
- 0 <= len(words) <= 10^4
- 1 <= len(words[i]) <= maxWidth <= 100
- Each word consists of non-space characters only
Examples
Input: (["The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"], 10)
Expected Output: ["The quick", "brown fox", "jumps over", "the lazy", "dog"]
Explanation: Each line greedily takes as many words as possible without exceeding width 10.
Input: (["a", "bc", "d", "ef"], 4)
Expected Output: ["a bc", "d ef"]
Explanation: Both lines fit exactly into width 4 with one space between words.