Text Justification
Problem
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
words = ["This","is","an","example"], maxWidth = 14["This is an", "example "]def full_justify(words, W):
out = []
i = 0
while i < len(words):
length = len(words[i])
j = i + 1
while j < len(words) and length + 1 + len(words[j]) <= W:
length += 1 + len(words[j])
j += 1
gaps = j - i - 1
if j == len(words) or gaps == 0:
line = " ".join(words[i:j])
line += " " * (W - len(line))
else:
total_chars = sum(len(w) for w in words[i:j])
total_spaces = W - total_chars
base = total_spaces // gaps
extra = total_spaces % gaps
parts = []
for k in range(i, j):
parts.append(words[k])
if k < j - 1:
parts.append(" " * (base + (1 if k - i < extra else 0)))
line = "".join(parts)
out.append(line)
i = j
return outfunction fullJustify(words, W) {
const out = [];
let i = 0;
while (i < words.length) {
let len = words[i].length, j = i + 1;
while (j < words.length && len + 1 + words[j].length <= W) {
len += 1 + words[j].length;
j++;
}
const gaps = j - i - 1;
let line;
if (j === words.length || gaps === 0) {
line = words.slice(i, j).join(" ");
line += " ".repeat(W - line.length);
} else {
const totalChars = words.slice(i, j).reduce((s, w) => s + w.length, 0);
const totalSpaces = W - totalChars;
const base = Math.floor(totalSpaces / gaps);
const extra = totalSpaces % gaps;
line = "";
for (let k = i; k < j; k++) {
line += words[k];
if (k < j - 1) {
line += " ".repeat(base + (k - i < extra ? 1 : 0));
}
}
}
out.push(line);
i = j;
}
return out;
}class Solution {
public List<String> fullJustify(String[] words, int W) {
List<String> out = new ArrayList<>();
int i = 0;
while (i < words.length) {
int len = words[i].length(), j = i + 1;
while (j < words.length && len + 1 + words[j].length() <= W) {
len += 1 + words[j].length(); j++;
}
int gaps = j - i - 1;
StringBuilder line = new StringBuilder();
if (j == words.length || gaps == 0) {
for (int k = i; k < j; k++) {
if (k > i) line.append(' ');
line.append(words[k]);
}
while (line.length() < W) line.append(' ');
} else {
int totalChars = 0;
for (int k = i; k < j; k++) totalChars += words[k].length();
int totalSpaces = W - totalChars;
int base = totalSpaces / gaps, extra = totalSpaces % gaps;
for (int k = i; k < j; k++) {
line.append(words[k]);
if (k < j - 1) {
int n = base + (k - i < extra ? 1 : 0);
for (int s = 0; s < n; s++) line.append(' ');
}
}
}
out.add(line.toString());
i = j;
}
return out;
}
}vector<string> fullJustify(vector<string>& words, int W) {
vector<string> out;
int i = 0;
while (i < (int)words.size()) {
int len = words[i].size(), j = i + 1;
while (j < (int)words.size() && len + 1 + (int)words[j].size() <= W) {
len += 1 + words[j].size(); j++;
}
int gaps = j - i - 1;
string line;
if (j == (int)words.size() || gaps == 0) {
for (int k = i; k < j; k++) {
if (k > i) line += ' ';
line += words[k];
}
line += string(W - line.size(), ' ');
} else {
int totalChars = 0;
for (int k = i; k < j; k++) totalChars += words[k].size();
int totalSpaces = W - totalChars;
int base = totalSpaces / gaps, extra = totalSpaces % gaps;
for (int k = i; k < j; k++) {
line += words[k];
if (k < j - 1) line += string(base + (k - i < extra ? 1 : 0), ' ');
}
}
out.push_back(line);
i = j;
}
return out;
}Explanation
The goal is to lay out words into lines of exactly maxWidth characters, fully justified. We do it greedily: cram as many words as fit on each line, then spread the leftover spaces so the line is perfectly wide.
The outer while loop starts each line at word i and pushes j forward while the next word still fits, using length + 1 + len(words[j]) <= W (the +1 reserves a single space between words). That gives the group of words for this line and the number of gaps between them.
To justify, we share the spare spaces among the gaps: base = total_spaces // gaps goes into every gap, and the leftover extra spaces are added one each to the leftmost gaps. That is why earlier gaps can be one space wider than later ones.
Two cases skip the fancy spreading: the last line, and any line with only one word. Those are left-justified with single spaces and then padded with spaces on the right to reach W.
Example: ["This","is","an","example"] with W = 14. The first line packs This is an (8 chars of letters, 6 spaces to spread over 2 gaps → 3 and 3), giving "This is an"-style spacing, while the final line "example" is left-justified and padded to width 14.