Fixed-Width Text Display
Company: Otter.Ai
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Fixed-Width Text Display
You are building a text display that renders a sequence of words inside a viewport of a **fixed character width** `maxWidth`. The display lays words out left to right, packing as many words as possible onto each line before wrapping to the next line.
The layout rule is the standard one used by word-wrapping renderers: when placing words on a line, consecutive words must be separated by **at least one space**. A word may be placed on the current line only if, after adding it (together with the single spaces that separate it from the words already on the line), the line's length does not exceed `maxWidth`. Otherwise the word starts a new line.
You are given a list of words `words` and an integer `maxWidth`. Every individual word satisfies `1 <= word.length <= maxWidth`, so every word fits on a line by itself.
This problem has two parts.
### Part 1 — Words per line (simplified)
Using the packing rule above with exactly **one** space between adjacent words, return a list of integers where the `i`-th element is the number of words placed on the `i`-th line.
Concretely, greedily fill each line: a word fits on the current line if `currentLength + 1 + word.length <= maxWidth`, where `currentLength` is the length of the words already on the line plus the single spaces between them (an empty line has `currentLength = 0` and the first word on a line never needs a leading space). When a word does not fit, it begins a new line.
**Example**
```
words = ["This", "is", "an", "example", "of", "text", "display"]
maxWidth = 16
Lines:
"This is an" (10 chars) -> 3 words
"example of text" (15 chars) -> 3 words
"display" (7 chars) -> 1 word
Output: [3, 3, 1]
```
### Part 2 — Full justification
Now render the actual lines as fully **justified** text, where every line is exactly `maxWidth` characters wide. Pack words greedily into lines using the same rule as Part 1 (at least one space between words), then format each line as follows:
- **Distribute extra spaces** between words so that the line is exactly `maxWidth` characters. If the spaces on a line do not divide evenly between the word gaps, the **left** gaps receive more spaces than the gaps on the right.
- A line that contains **only one word**, and the **last line** of the output, are **left-justified**: words are separated by a single space and the remaining characters on the right are padded with spaces to reach `maxWidth`.
Return the list of formatted lines, each a string of length exactly `maxWidth`.
**Example**
```
words = ["This", "is", "an", "example", "of", "text", "justification"]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification "
]
```
(The first line has two gaps and 4 extra spaces, split 2/2; the second line has two gaps and 2 extra spaces, split 1/1; the last line is left-justified and right-padded.)
### Input / Output
- `words`: a list of strings, each containing no spaces, with `1 <= words.length` and `1 <= word.length <= maxWidth`.
- `maxWidth`: a positive integer.
- Part 1 returns a list of integers (word counts per line).
- Part 2 returns a list of strings, each of length exactly `maxWidth`.
Quick Answer: This question tests a candidate's ability to implement greedy line-packing and space-distribution algorithms, core string manipulation skills evaluated in software engineering interviews. It assesses practical application of text layout logic, including handling edge cases like single-word lines and justified formatting with uneven space distribution.
Fixed-Width Text Display — Part 1: Words Per Line
You are building a text display that renders a sequence of words inside a viewport of a fixed character width `maxWidth`. Words are laid out left to right, packing as many words as possible onto each line before wrapping to the next.
Using the standard greedy packing rule with exactly **one** space between adjacent words, return a list of integers where the i-th element is the number of words placed on the i-th line.
A word fits on the current line if `currentLength + 1 + word.length <= maxWidth`, where `currentLength` is the length of the words already on the line plus the single spaces between them. An empty line has `currentLength = 0` and the first word on a line never needs a leading space. When a word does not fit, it begins a new line. Every word satisfies `1 <= word.length <= maxWidth`, so every word fits on a line by itself.
Example: `words = ["This", "is", "an", "example", "of", "text", "display"]`, `maxWidth = 16` -> `[3, 3, 1]` (lines: "This is an", "example of text", "display").
Constraints
- 1 <= words.length
- 1 <= word.length <= maxWidth
- Each word contains no spaces
- maxWidth is a positive integer
Examples
Input: (["This", "is", "an", "example", "of", "text", "display"], 16)
Expected Output: [3, 3, 1]
Explanation: Lines: 'This is an' (10), 'example of text' (15), 'display' (7).
Input: (["a"], 5)
Expected Output: [1]
Explanation: A single word forms one line by itself.
Input: (["hello", "world"], 5)
Expected Output: [1, 1]
Explanation: Each word is exactly width 5, so 'hello world' (11) exceeds maxWidth; each word gets its own line.
Input: (["aa", "bb", "cc", "dd"], 5)
Expected Output: [2, 2]
Explanation: 'aa bb' = 5 chars fits exactly; adding 'cc' would be 8 > 5, so it wraps. Same for the second line.
Input: (["one", "two", "three", "four"], 11)
Expected Output: [2, 2]
Explanation: 'one two' = 7 fits; +'three' = 13 > 11 wraps. 'three four' = 10 <= 11 fits.
Input: (["x", "x", "x", "x", "x"], 9)
Expected Output: [5]
Explanation: 'x x x x x' = 9 chars fits exactly on one line.
Hints
- Greedily fill each line: track the current line length (words plus single separating spaces).
- A word fits if currentLength + 1 + len(word) <= maxWidth; the first word on a line needs no leading space.
- When a word doesn't fit, push the current line's word count to the result and start a fresh line with that word. Don't forget the final line after the loop.
Fixed-Width Text Display — Part 2: Full Justification
Now render the actual lines as fully **justified** text, where every line is exactly `maxWidth` characters wide. Pack words greedily into lines using the same rule as Part 1 (at least one space between words), then format each line:
- **Distribute extra spaces** between words so the line is exactly `maxWidth` characters. If the spaces don't divide evenly between the word gaps, the **left** gaps receive more spaces than the gaps on the right.
- A line that contains **only one word**, and the **last line** of the output, are **left-justified**: words separated by a single space and the remaining characters padded on the right with spaces to reach `maxWidth`.
Return the list of formatted lines, each a string of length exactly `maxWidth`.
Example: `words = ["This", "is", "an", "example", "of", "text", "justification"]`, `maxWidth = 16` -> `["This is an", "example of text", "justification "]`. (First line: two gaps, 4 extra spaces split 2/2. Second line: two gaps, 2 extra spaces split 1/1. Last line left-justified and right-padded.)
Constraints
- 1 <= words.length
- 1 <= word.length <= maxWidth
- Each word contains no spaces
- Each returned line has length exactly maxWidth
- maxWidth is a positive integer
Examples
Input: (["This", "is", "an", "example", "of", "text", "justification"], 16)
Expected Output: ["This is an", "example of text", "justification "]
Explanation: Line 1: two gaps, 4 extra spaces split 2/2. Line 2: two gaps, 2 extra spaces split 1/1. Last line left-justified, right-padded.
Input: (["What", "must", "be", "acknowledgment", "shall", "be"], 16)
Expected Output: ["What must be", "acknowledgment ", "shall be "]
Explanation: Line 2 has a single word so it is left-justified and padded. The last line is left-justified.
Input: (["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"], 20)
Expected Output: ["Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do "]
Explanation: Classic case. Line 4 'a computer. Art is' has 3 gaps and 5 extra spaces distributed 2/2/1 (left gaps get more).
Input: (["a"], 5)
Expected Output: ["a "]
Explanation: Single word and last line: left-justified, right-padded to width 5.
Input: (["hello"], 5)
Expected Output: ["hello"]
Explanation: The word exactly fills the width; no padding needed.
Input: (["ab", "cd", "ef"], 6)
Expected Output: ["ab cd", "ef "]
Explanation: Line 1 'ab cd' is fully justified: one gap, 2 extra spaces -> 'ab cd'. Last line 'ef' left-justified and padded.
Hints
- Pack words greedily exactly as in Part 1, but accumulate the actual words on each line.
- For a fully-justified line with k words there are k-1 gaps; spaces = maxWidth - sum(word lengths). Give each gap base = spaces // gaps, then add one extra space to the leftmost `spaces % gaps` gaps.
- Two special cases are left-justified instead: a line with a single word, and the final line. Join with single spaces and right-pad with spaces to maxWidth.