Text Justification

Hard

#0068Time: O(N * maxWidth)Space: O(N * maxWidth)33 companies

Data structures

Companies

Prompt

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:

A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array 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 <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100
words[i].length <= maxWidth

Approaches

1 approach with complexity analysis and trade-offs.

This problem requires a greedy approach to pack words into lines and then format them. The most direct way to solve this is to simulate the process line by line. For each line, we first determine the maximum number of words that can fit, and then we apply the specific justification rules based on whether it's a regular line, the last line, or a line with a single word.

Algorithm

Initialize an empty list result to store the formatted lines and an index i = 0 to track the current word.
Loop while i is less than the total number of words:
- Determine words for the current line: Greedily find the range of words [i, j-1] that can fit on the current line. Start with words[i] and keep adding subsequent words as long as the total length (including at least one space between words) does not exceed maxWidth.
- Format the identified line:
  - Left Justification: If the line is the last line of text (j reaches the end of the words array) or contains only a single word, it should be left-justified. This means words are separated by a single space, and the rest of the line is padded with spaces on the right.
  - Full Justification: For all other lines, the spaces need to be distributed as evenly as possible between the words. Calculate the base number of spaces for each gap and distribute any extra spaces one by one to the gaps on the left.
- Add the newly formatted line to the result list.
- Update the index i to j to start processing the next line.
Return the result list.

Walkthrough

The algorithm iterates through the words, processing one line at a time. In each step, it identifies a contiguous block of words that can fit onto a single line. Once these words are identified, it calculates the necessary spacing and constructs the formatted line string. This process is repeated until all words have been placed.

Algorithm Steps:
1. Initialize an empty list result to store the formatted lines and an index i = 0 to track the current word.
2. Loop while i is less than the total number of words: a. Determine words for the current line: Greedily find the range of words [i, j-1] that can fit on the current line. Start with words[i] and keep adding subsequent words as long as the total length (including at least one space between words) does not exceed maxWidth. b. Format the identified line: * Left Justification: If the line is the last line of text (j reaches the end of the words array) or contains only a single word, it should be left-justified. This means words are separated by a single space, and the rest of the line is padded with spaces on the right. * Full Justification: For all other lines, the spaces need to be distributed as evenly as possible between the words. Calculate the base number of spaces for each gap and distribute any extra spaces one by one to the gaps on the left. c. Add the newly formatted line to the result list. d. Update the index i to j to start processing the next line.
3. Return the result list.
Code Snippet:

import java.util.ArrayList; import java.util.List;

class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> result = new ArrayList<>(); int i = 0; int n = words.length;

1    while (i < n) {2        // 1. Determine words for the current line3        int j = i + 1;4        int lineLength = words[i].length();5        while (j < n && (lineLength + words[j].length() + (j - i)) <= maxWidth) {6            lineLength += words[j].length();7            j++;8        }9 10        int numWords = j - i;11        int totalSpaces = maxWidth - lineLength;12 13        StringBuilder line = new StringBuilder();14 15        // 2. Format the line16        // Case 1: Last line or single-word line (Left Justification)17        if (numWords == 1 || j == n) {18            line.append(words[i]);19            for (int k = i + 1; k < j; k++) {20                line.append(" ").append(words[k]);21            }22            int remainingSpaces = maxWidth - line.length();23            appendSpaces(line, remainingSpaces);24        } else {25        // Case 2: Regular line (Full Justification)26            int numGaps = numWords - 1;27            int spacesPerGap = totalSpaces / numGaps;28            int extraSpaces = totalSpaces % numGaps;29 30            line.append(words[i]);31            for (int k = i + 1; k < j; k++) {32                int spacesToApply = spacesPerGap + (extraSpaces > 0 ? 1 : 0);33                appendSpaces(line, spacesToApply);34                line.append(words[k]);35                extraSpaces--;36            }37        }38        39        result.add(line.toString());40        i = j; // Move to the start of the next line41    }42 43    return result;44}45 46private void appendSpaces(StringBuilder sb, int count) {47    for (int k = 0; k < count; k++) {48        sb.append(" ");49    }50}

} ```

Complexity

Time

O(N * maxWidth)

Space

O(N * maxWidth)

Trade-offs

Pros

It's a direct simulation of the process described in the problem.
It's efficient and passes within the given constraints.
The greedy choice at each step (packing as many words as possible) is exactly what the problem requires.

Cons

The logic can be tricky to implement correctly, with several edge cases to handle (last line, single-word line, space distribution).
The code can become lengthy due to the different formatting rules.

Solutions

Solution

1public class Solution {2    public IList < string > FullJustify(string[] words, int maxWidth) {3        var ans = new List < string > ();4        for (int i = 0, n = words.Length; i < n;) {5            var t = new List < string > ();6            t.Add(words[i]);7            int cnt = words[i].Length;8            ++i;9            while (i < n && cnt + 1 + words[i].Length <= maxWidth) {10                t.Add(words[i]);11                cnt += 1 + words[i].Length;12                ++i;13            }14            if (i == n || t.Count == 1) {15                string left = string.Join(" ", t);16                string right = new string(' ', maxWidth - left.Length);17                ans.Add(left + right);18                continue;19            }20            int spaceWidth = maxWidth - (cnt - t.Count + 1);21            int w = spaceWidth / (t.Count - 1);22            int m = spaceWidth % (t.Count - 1);23            var row = new StringBuilder();24            for (int j = 0; j < t.Count - 1; ++j) {25                row.Append(t[j]);26                row.Append(new string(' ', w + (j < m ? 1 : 0)));27            }28            row.Append(t[t.Count - 1]);29            ans.Add(row.ToString());30        }31        return ans;32    }33}

1class Solution {2public3  List<String> fullJustify(String[] words, int maxWidth) {4    List<String> ans = new ArrayList<>();5    for (int i = 0, n = words.length; i < n;) {6      List<String> t = new ArrayList<>();7      t.add(words[i]);8      int cnt = words[i].length();9      ++i;10      while (i < n && cnt + 1 + words[i].length() <= maxWidth) {11        cnt += 1 + words[i].length();12        t.add(words[i++]);13      }14      if (i == n || t.size() == 1) {15        String left = String.join(" ", t);16        String right = " ".repeat(maxWidth - left.length());17        ans.add(left + right);18        continue;19      }20      int spaceWidth = maxWidth - (cnt - t.size() + 1);21      int w = spaceWidth / (t.size() - 1);22      int m = spaceWidth % (t.size() - 1);23      StringBuilder row = new StringBuilder();24      for (int j = 0; j < t.size() - 1; ++j) {25        row.append(t.get(j));26        row.append(" ".repeat(w + (j < m ? 1 : 0)));27      }28      row.append(t.get(t.size() - 1));29      ans.add(row.toString());30    }31    return ans;32  }33}

1class Solution {2public:3  vector<string> fullJustify(vector<string> &words, int maxWidth) {4    vector<string> ans;5    for (int i = 0, n = words.size(); i < n;) {6      vector<string> t = {words[i]};7      int cnt = words[i].size();8      ++i;9      while (i < n && cnt + 1 + words[i].size() <= maxWidth) {10        cnt += 1 + words[i].size();11        t.emplace_back(words[i++]);12      }13      if (i == n || t.size() == 1) {14        string left = t[0];15        for (int j = 1; j < t.size(); ++j) {16          left += " " + t[j];17        }18        string right = string(maxWidth - left.size(), ' ');19        ans.emplace_back(left + right);20        continue;21      }22      int spaceWidth = maxWidth - (cnt - t.size() + 1);23      int w = spaceWidth / (t.size() - 1);24      int m = spaceWidth % (t.size() - 1);25      string row;26      for (int j = 0; j < t.size() - 1; ++j) {27        row += t[j] + string(w + (j < m ? 1 : 0), ' ');28      }29      row += t.back();30      ans.emplace_back(row);31    }32    return ans;33  }34};

1''' Explanation: - The function `fullJustify` takes a list of words and a maximum width `maxWidth` as inputs. - It iterates over each word, deciding whether to add the current word to the current line (`cur`) or to start a new line. - If adding the current word to the line would exceed `maxWidth`, it justifies the current line by adding extra spaces between words as needed, then starts a new line. - Once all words are processed, it left-justifies the last line by joining the remaining words in `cur` with a single space and then using `.ljust(maxWidth)` to ensure the line is of maximum width. - The result is a list of strings, where each string represents a justified line of text. This solution carefully handles edge cases, such as when there's only one word in the line (avoiding division by zero) and ensuring the last line is left-justified instead of fully justified. ''' ''' >>> cur = [1] >>> len(cur) - 1 0 >>> ( len(cur) - 1 or 1 ) 1 ''' ''' # api: string.ljust(width[, fillchar]) >>> "Hello".ljust(10) 'Hello ' >>> "Hello".ljust(10, '-') 'Hello-----' >>> "Hello".ljust(2) 'Hello' >>> "Hello World".ljust(20) 'Hello World ' >>> "Hello World".ljust(20, '-') 'Hello World---------' # api: string.rjust(width[, fillchar]) >>> "Hello".rjust(10) ' Hello' >>> "Hello".rjust(10, '-') '-----Hello' >>> "Hello".rjust(2) 'Hello' >>> "Hello World".rjust(20) ' Hello World' >>> "Hello World".rjust(20, '-') '---------Hello World' ''' class Solution : def fullJustify ( self , words : List [ str ], maxWidth : int ) -> List [ str ]: res , cur , num_of_letters = [], [], 0 for w in words : # len(cur) is the space count, from last round, right one less after adding 'w' if num_of_letters + len ( cur ) + len ( w ) > maxWidth : for i in range ( maxWidth - num_of_letters ): # The "or 1" part is for dealing with the edge case 'len(cur) == 1' cur [ i % ( len ( cur ) - 1 or 1 )] += ' ' res . append ( '' . join ( cur )) cur , num_of_letters = [], 0 cur += [ w ] num_of_letters += len ( w ) return res + [ ' ' . join ( cur ). ljust ( maxWidth )] ############ ''' >>> 17 % 3 2 >>> divmod(17,3) (5, 2) ''' ''' >>> ['This', 'is', 'an'] ['This', 'is', 'an'] >>> t = ['This', 'is', 'an'] >>> spaces = [' ', ' '] # note: here j starts from 0 >>> for j, word in enumerate(t[1:]): ... print(j) ... print(word) ... 0 is 1 an ''' class Solution : def fullJustify ( self , words : List [ str ], maxWidth : int ) -> List [ str ]: def partition ( n , cnt ): base , mod = divmod ( n , cnt ) res = [ f " { ' ' * ( base + ( i < mod )) } " for i in range ( cnt )] return res ans = [] i , n = 0 , len ( words ) while i < n : # one line per iteration t = [ words [ i ]] cnt = len ( words [ i ]) i += 1 # move to next word while i < n and cnt + 1 + len ( words [ i ]) <= maxWidth : # greedy search for one line cnt += 1 + len ( words [ i ]) t . append ( words [ i ]) i += 1 if i == n or len ( t ) == 1 : # this is the last line or only one (super-long) word in a line left = ' ' . join ( t ) right = ' ' * ( maxWidth - len ( left )) ans . append ( f " { left }{ right } " ) continue # so i != n , so only one word, no need to add spaces. # e.g. a word with the same length as maxWidth, # or, e.g. the 2nd word is super long and cannot fit in current line # if i==n, then will not enter next while words_width = cnt - ( len ( t ) - 1 ) # pure words total length, with no spaces # spaces in-between these words in t[]: len(t) - 1 space_width = maxWidth - words_width spaces = partition ( space_width , len ( t ) - 1 ) sb = [ t [ 0 ]] # 1st word of this line, no space before it for j , word in enumerate ( t [ 1 :]): # last word has no following space sb . append ( spaces [ j ]) # j starts from 0 sb . append ( word ) ans . append ( '' . join ( sb )) return ans ########### class Solution : def fullJustify ( self , words : List [ str ], maxWidth : int ) -> List [ str ]: left = 0 result = [] while left < len ( words ): right = self . findRight ( left , words , maxWidth ) result . append ( self . justify ( left , right , words , maxWidth )) left = right + 1 return result def findRight ( self , left , words , maxWidth ): right = left word_length = len ( words [ right ]) while ( right + 1 ) < len ( words ) and ( word_length + 1 + len ( words [ right + 1 ])) <= maxWidth : right += 1 word_length += 1 + len ( words [ right ]) return right def justify ( self , left , right , words , maxWidth ): if right - left == 0 : return self . padResult ( words [ left ], maxWidth ) is_last_line = ( right == len ( words ) - 1 ) num_spaces = right - left total_space = maxWidth - self . wordsLength ( left , right , words ) space = " " if is_last_line else " " * ( total_space // num_spaces ) remainder = 0 if is_last_line else total_space % num_spaces result = "" for i in range ( left , right ): result += words [ i ] result += space if remainder > 0 : result += " " remainder -= 1 result += words [ right ] result += " " * ( maxWidth - len ( result )) return result def wordsLength ( self , left , right , words ): words_length = 0 for i in range ( left , right + 1 ): words_length += len ( words [ i ]) return words_length def padResult ( self , result , maxWidth ): return result + " " * ( maxWidth - len ( result ))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem