Problem

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

OR

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.

Your program should return a list of strings, where each string represents a single line.

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

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.

Solution

There is not a special algorithm required to solve this problem. To correctly solve this problem, the following situations should be taken care of:

  1. if a line has only one word and the word’s length is less than max width, we need to fill the left part with spaces.
  2. how to distribute extra spaces for each words when the number of spaces can not be evenly distributed to each word.

Method 1 - Modular Iterative Approach 🏆

We start with left being the first word.

findRight: Then we greedily try to go as far right as possible until we fill our current line.

Then we justify one line at a time.

justify: In all cases we pad the right side with spaces until we reach max width for the line;

  1. If it’s one word then it is easy, the result is just that word.
  2. If it’s the last line then the result is all words separated by a single space.
  3. Otherwise we calculate the size of each space evenly and if there is a remainder we distribute an extra space until it is gone.

Code:

public List<String> fullJustify(String[] words, int maxWidth) {
	int left = 0;
	List<String> ans = new ArrayList<>();

	while (left < words.length) {
		int right = findRight(left, words, maxWidth);
		ans.add(justify(left, right, words, maxWidth));
		left = right + 1;
	}

	return ans;
}

private int findRight(int left, String[] words, int maxWidth) {
	int right = left;
	int sum = words[right++].length();
	// we are doing sum+1 because after each word, a space follows
	while (right < words.length && (sum + 1 + words[right].length()) <= maxWidth) {
		sum += 1 + words[right++].length();
	}
	return right - 1;
}

private String justify(int left, int right, String[] words, int maxWidth) {
	// only one word
	if (right == left) {
		return padRight(words[left], maxWidth);
	}

	boolean isLastLine = right == words.length - 1;

	int numSpaceSlots = right - left; // words are right-left+1
	int totalSpace = maxWidth - wordsLength(left, right, words);

	int numSpacesBetween = isLastLine ? 1 : totalSpace / numSpaceSlots;
	String spaceBetween = whitespace(numSpacesBetween);

	int remainingSpaceCount = isLastLine ? 0 : totalSpace % numSpaceSlots;

	StringBuilder lineSB = new StringBuilder();
	for (int i = left; i <= right; i++) {
		lineSB.append(words[i]);
		lineSB.append(spaceBetween);// add allocated space
		lineSB.append(remainingSpaceCount-- > 0 ? " " : ""); // add more space if remainder space exists
	}
	// note: No need to check if last line, because we have already adjusted space accordingly earlier
	return padRight(lineSB.toString().trim(), maxWidth);
}

private int wordsLength(int left, int right, String[] words) {
	int wordsLength = 0;
	for (int i = left; i <= right; i++) {
		wordsLength += words[i].length();
	}
	return wordsLength;
}

private String padRight(String result, int maxWidth) {
	return result + whitespace(maxWidth - result.length());
}

private String whitespace(int length) {
	// old method
	// return new String(new char[length]).replace('\0', ' ');
	return " ".repeat(length);
}

Method 2 - Another Iterative Approach

public List<String> fullJustify(String[] words, int maxWidth) {
	List<String> result = new ArrayList<String> ();

	if (words == null || words.length == 0) {
		return result;
	}

	int count = 0;
	int last = 0;
	ArrayList<String> list = new ArrayList<String> ();
	for (int i = 0; i<words.length; i++) {
		count = count + words[i].length();

		if (count + i - last > maxWidth) {
			int wordsLen = count - words[i].length();
			int spaceLen = maxWidth - wordsLen;
			int eachLen = 1;
			int extraLen = 0;

			if (i - last - 1 > 0) {
				eachLen = spaceLen / (i - last - 1);
				extraLen = spaceLen % (i - last - 1);
			}

			StringBuilder sb = new StringBuilder();

			for (int k = last; k<i - 1; k++) {
				sb.append(words[k]);

				int ce = 0;
				while (ce<eachLen) {
					sb.append(" ");
					ce++;
				}

				if (extraLen > 0) {
					sb.append(" ");
					extraLen--;
				}
			}

			sb.append(words[i - 1]); //last words in the line
			//if only one word in this line, need to fill left with space
			while (sb.length()<maxWidth) {
				sb.append(" ");
			}

			result.add(sb.toString());

			last = i;
			count = words[i].length();
		}
	}

	int lastLen = 0;
	StringBuilder sb = new StringBuilder();

	for (int i = last; i<words.length - 1; i++) {
		count = count + words[i].length();
		sb.append(words[i] + " ");
	}

	sb.append(words[words.length - 1]);
	int d = 0;
	while (sb.length()<maxWidth) {
		sb.append(" ");
	}
	result.add(sb.toString());

	return result;
}