Задача с собеседования в AirBnB

Дан массив строк (слов) и максимальная ширина maxWidth.
Вам необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов, и была полностью выровнена по ширине (слева и справа)

При необходимости нужно добавлять дополнительные пробелы, чтобы в каждой строке было ровно maxWidth символов. Они должны быть распределены как можно более равномерно. Если количество пробелов в строке неравномерно распределяется между словами, то слева будет больше пробелов, чем справа.

Последняя строка должна быть выровнена по левому краю, а между словами не должно быть лишних пробелов (только для последней строки)

Пример:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]

Наш чат алгоритмистов

Решение:
Мы жадно упаковываем слова в строку, пока добавление следующего слова (с хотя бы одним пробелом) не превысит max_width, для каждой непоследней строки равномерно распределяем требуемые пробелы по промежуткам (избыточные пробелы даём левым промежуткам), а последнюю строку и строки из одного слова выравниваем по левому краю; реализация проходит по словам один раз и формирует финальные строки, поэтому время работы - O(C+W), где C — суммарное число символов в словах, W — число слов

def fullJustify(self, words: List[str], max_width: int) -> List[str]:
res: List[str] = []
n = len(words)
i = 0

while i < n:
j = i + 1
line_len = len(words[i])
while j < n and line_len + 1 + len(words[j]) <= max_width:
line_len += 1 + len(words[j])
j += 1

line_words = words[i:j]
num_words = j - i

if j == n or num_words == 1:
line = " ".join(line_words)
line += " " * (max_width - len(line))
else:
total_chars = sum(len(w) for w in line_words)
total_spaces = max_width - total_chars
slots = num_words - 1
base_space, extra = divmod(total_spaces, slots)

parts: List[str] = []
for k in range(slots):
parts.append(line_words[k])
parts.append(" " * (base_space + (1 if k < extra else 0)))
parts.append(line_words[-1])
line = "".join(parts)

res.append(line)
i = j

return res

@algoses