Text Justification

This page explains Java solution to problem Text Justification using Greedy algorithm.

Problem Statement

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.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do 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.

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 " ]

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class TextJustification {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int index = 0;
        int width = 0;
        int widthWithoutSpace = 0;
        int fitting = 0;
        int start = 0;
        List<String> res = new ArrayList<>();

        while(index < words.length) {
            if(width + words[index].length() <= maxWidth) {
                width = Math.min(maxWidth, width + words[index].length() + 1);
                widthWithoutSpace = widthWithoutSpace + words[index].length();
                fitting++;
                index++;
            }
            else {
                format(words, width, widthWithoutSpace, maxWidth, start, fitting, res);
                width = 0;
                widthWithoutSpace = 0;
                fitting = 0;
                start = index;
            }
        }
        if(fitting > 0) format(words, width, widthWithoutSpace, maxWidth, start, fitting, res);
        return res;
    }

    private void format(String[] words, int width, int widthWithoutSpace, int maxWidth,
                        int start, int fitting,
                        List<String> res) {
        /**
         *   We will want last line to be left justified
         *   So if it is only one word or if it is last line, just append one spaces
         *   And append remainingSpaces later
         **/
        if(fitting == 1 || start + fitting == words.length) {
            StringBuilder sb = new StringBuilder();
            int index = 0;
            while(index < fitting) {
                sb.append(words[start + index]);
                if(index < fitting - 1) sb.append(" ");
                index++;
            }
            int remainingSpaces = maxWidth - (widthWithoutSpace + fitting - 1);
            for(int space = 0; space < remainingSpaces; space++) sb.append(" ");
            res.add(sb.toString());
        }
        else {
            int index = 0;
            int totalSpaces = maxWidth - widthWithoutSpace;
            int spaces = totalSpaces / (fitting - 1);
            int remainingSpaces = totalSpaces % (fitting - 1);
            StringBuilder sb = new StringBuilder();
            while(index < fitting) {
                sb.append(words[start + index]);
                if(index < fitting - 1) {
                    for(int s = 0; s < spaces; s++) sb.append(" ");
                    if(remainingSpaces-- > 0) sb.append(" ");
                }
                index++;
            }
            res.add(sb.toString());
        }
    }
}

Time Complexity

O(N) Where
N is total number of characters in words input string array

Space Complexity

O(N) Where
N is total number of characters in words input string array