Text Justification Algorithm (LeetCode)

Here is a step by step explanation of a LeetCode hard problem called "Text Justification". This problem is extremely popular in technical interviews and is asked at Google, Intuit, Indeed, LinkedIn, Coursera, Pinterest, Uber, Snapchat, Amazon, and Twilio.

Check out my interview prep platform for learning the patterns!
? Interview Prep Platform: https://algoswithmichael.com

? Join the community Discord: https://discord.gg/aVWsAaaCtT
? Support me on Patreon: https://www.patreon.com/michaelmuinos
?Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos
?Follow me on Github: https://github.com/MichaelMuinos

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 is in the top 50 lowest acceptance rates out of all 1500 LeetCode problems on the platform sitting at about 27 percent.

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.