Given an array of strings 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.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
0 and not exceed maxWidth.words contains at least one word.Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [ "This is an", "example of text", "justification. " ]
Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 Output: [ "What must be", "acknowledgment ", "shall be " ] Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word.
Example 3:
Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20 Output: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]
Constraints:
1 <= words.length <= 3001 <= words[i].length <= 20words[i] consists of only English letters and symbols.1 <= maxWidth <= 100words[i].length <= maxWidthThe Text Justification problem is typically solved using a greedy simulation approach. The idea is to process the list of words and build lines one by one while ensuring each line does not exceed the given maximum width. For each line, keep adding words until adding another word would exceed maxWidth.
Once the words for a line are selected, distribute the required spaces between them so the total length becomes exactly maxWidth. Spaces should be distributed as evenly as possible from left to right. If the spaces cannot be divided evenly, the left gaps receive extra spaces. The final line is treated differently—it is left-justified, meaning words are separated by a single space and the remaining spaces are added at the end.
This approach processes each word once and simulates spacing distribution efficiently, resulting in a linear pass over the input.
Time Complexity: O(n) where n is the total number of words (or characters processed). Space Complexity: O(1) auxiliary space excluding the output.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Line Building with Space Distribution | O(n) | O(1) auxiliary (excluding output) |
Tushar Roy - Coding Made Simple
This approach involves iterating through the given words and greedily forming a line by adding as many words as possible without exceeding the maxWidth. When a line is completed, the algorithm distributes spaces evenly between words. If the number of spaces doesn’t divide evenly, more spaces are added to the left slots. The last line is treated differently by left-justifying the text.
Time Complexity: O(n), where n is the total number of characters in all words.
Space Complexity: O(n), where n is the number of lines formed times maxWidth for the justified text.
1import java.util.*;
2
3public class TextJustification {
4 public List<String> fullJustify(String[] words, int maxWidth) {
5 List<String> result = new ArrayList<>();
6 int index = 0;
7 while (index < words.length) {
8 int totalChars = words[index].length();
9 int last = index + 1;
10 while (last < words.length) {
11 if (totalChars + words[last].length() + 1 > maxWidth) break;
12 totalChars += words[last].length() + 1;
13 last++;
14 }
15
16 StringBuilder sb = new StringBuilder();
17 int diff = last - index - 1;
18 // if last line or number of words in the line is 1, left-justify
19 if (last == words.length || diff == 0) {
20 for (int i = index; i < last; i++) {
21 sb.append(words[i]).append(" ");
22 }
23 sb.deleteCharAt(sb.length() - 1);
24 while (sb.length() < maxWidth) {
25 sb.append(" ");
26 }
27 } else {
28 int spaces = (maxWidth - totalChars) / diff;
29 int remainder = (maxWidth - totalChars) % diff;
30 for (int i = index; i < last - 1; i++) {
31 sb.append(words[i]).append(" ");
32 for (int j = 0; j < spaces + (i - index < remainder ? 1 : 0); j++) {
33 sb.append(" ");
34 }
35 }
36 sb.append(words[last - 1]);
37 }
38 result.add(sb.toString());
39 index = last;
40 }
41 return result;
42 }
43}This Java implementation uses a while loop to process words. It determines the range of words that can fit into the current line, then builds the line accordingly. It checks if it's the last line or if only one word exists in the line, in which case left-justification is applied. Otherwise, the spaces are evenly distributed.
This method leverages dynamic programming to minimize a hypothetical cost function that combines badness or uneven space distribution along with total number of lines used, aiming to determine the optimal setup of words per line.
Time Complexity: O(n^2), due to potential double iterations required for exploring word positions.
Space Complexity: O(n), since it uses extra space for storing dp and path arrays.
1using System;
2using System.Collections.Generic;
3using System.Text;
4
5public class Solution {
public IList<string> FullJustify(string[] words, int maxWidth) {
int n = words.Length;
int[] dp = new int[n + 1];
int[] path = new int[n];
Array.Fill(dp, int.MaxValue);
dp[n] = 0;
for (int i = n - 1; i >= 0; i--) {
int lineLength = -1;
for (int j = i; j < n && lineLength <= maxWidth; j++) {
lineLength += words[j].Length + 1;
if (lineLength - 1 <= maxWidth) {
int lastCost = j == n - 1 ? 0 : maxWidth - (lineLength - 1);
if (dp[i] > dp[j + 1] + lastCost) {
dp[i] = dp[j + 1] + lastCost;
path[i] = j + 1;
}
}
}
}
List<string> result = new List<string>();
int k = 0;
while (k < words.Length) {
int end = path[k];
StringBuilder line = new StringBuilder(words[k]);
for (int i = k + 1; i < end; i++) {
line.Append(' ').Append(words[i]);
}
line.Append(new string(' ', maxWidth - line.Length));
result.Add(line.ToString());
k = end;
}
return result;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Text Justification is a common interview-style problem that tests string manipulation, greedy thinking, and attention to detail. Variants of this problem have appeared in coding interviews at large tech companies.
Arrays or lists are typically used to store the words for the current line. String builders or similar structures help efficiently construct the final justified line with properly distributed spaces.
The optimal approach uses a greedy strategy. You group as many words as possible into each line without exceeding the maximum width, then distribute spaces evenly between words. Special handling is applied to the last line, which is left-justified.
The challenge lies in correctly distributing spaces between words and handling edge cases such as single-word lines and the final left-justified line. Careful simulation and string manipulation are required to meet all formatting constraints.
This C# implementation also utilizes dynamic programming to find the least-cost configuration of lines based on word inclusion. The resulting justified lines respect the discovered optimal path ensuring the efficient use of space on each line.