Text Justification Algorithm

What is Text Justification?

Text justification will ensure that text that is multi-lined will be both left and right justified when displayed to the user.

How do you solve the LeetCode question Text Justification?

To solve this problem, there are two different approaches: dynamic programming OR greedy. In this video explanation, I am going to go over the greedy approach. This problem is very difficult and has close to a 30% success rate to pass. Using the greedy approach is in my opinion more simple to understand than the dynamic programming approach, but the caveat is that it is a slower approach.

Video Explanation of Text Justification LeetCode Question # 68

This video will explain the greedy approach for solving the Text Justification problem on LeetCode. The greedy approach involves having two pointers "i" and "j". We move our "j" pointer forward until we get to a point where the words in the line go over our "maxWidth" parameter. Once that occurs, we now know all of the words that are going to be inside of the line.

Next, we will count the number of words we have in the line. If we have a single word OR we are on the last line, then we will be left justifying the line, otherwise we middle justify. To left justify a line, we take the difference between the total amount of word characters we have and our "maxWidth" and this will tell us how many spaces there needs to be inside of the line. There should only be a single space between each word, but the last word will have the rest of the unused spaces to the very right of it, causing the line to left justify properly. In order to middle justify, we take the the number of spaces needed and the number of sections of spaces required. To get the section number, we do "j" - "i" - 1. Then divide our spaces with the section number which gives us a number to evenly distribute the spaces in between each word in the line. If we have extra spaces, the spaces will be added to the left-most words from left to right.

The time and space complexity of our solution is going to be O(lines * maxWidth). We must iterate, for each potential line, to the "maxWidth" since the spaces will be repeated. Under the hood, the "repeat" function is just running a for loop duplicating the character.

Quick Answers

How do you implement a text justification algorithm?

You can use dynamic programming or write a greedy algorithm.