A Racket Solution For LeetCode Problem #68 Text Justification

The high level approach is:

1. Group the words in a way that each group has at most “maxWidth” characters.
   • If there’s more than one word in a group, then at least one space will be added between each word, which must be accounted for in making sure words fit in groups.
2. Per group, determine how many characters are in a “lesser” space and how many characters are in a “bigger” space.
3. Determine how many “bigger” and “lesser” spaces there need to be. One word groups and the last group get left justified.
4. Add the spaces between words in each group.

This is the most interesting part of this exercise, I think.

This step is the most difficult. The difficulty lies in the fact that not all space between words will be the same. But, the larger spaces will only be one space character longer, so it isn’t too complicated. This is the simple case of adding spaces to the end of a single-word group which I will not go into

[(= 1 (length words)) 
 (string-append 
  (car words) 
  (make-string (- maxWidth (string-length (car words))) #\space))]

This is the main padding logic.

(let*-values (((words-to-pad) (length (cdr words)))
              ((lspace-len) (quotient spaces words-to-pad))
              ((lspace) (make-string lspace-len #\space))
              ((bspace-len) (ceiling (/ spaces words-to-pad)))
              ((bspace) (make-string bspace-len #\space))
              ((btimes) (- spaces (* words-to-pad lspace-len)))
              ((bw lw) (split-at words (add1 btimes))))
  (string-append
   (string-join bw bspace)
   (if (null? lw) "" (string-join lw lspace #:before-first lspace))))])))

These are the steps:

1. How many words do we have to pad? Padding in this case is prepending space before a word. Only words after the first need to be padded. Hence (length (cdr words)) is used.
2. How many spaces for a smaller pad is the quotient of spaces needed to fill the group to meet maxWidth, and words-to-pad. This might be all the pads we need. If there is any remainder in spaces, the bigger spaces will take care of it. So with a width of 10, and 4 words, with 5 characters, we end up with 5 spaces left. ………. ay..e..i.o 5 spaces / 3 words (quotient) is 1, the lesser pad length
3. Create the lesser space pad string for use later.
4. The bigger space length will be the ceiling of the ratio between remaining spaces and words to pad. Now that I think of it, I’m pretty sure this will always be one space larger and can just be (add1 lspace-len) but I don’t feel like running it through all the tests again on LeetCode. An exercise for the reader, perhaps?
5. Create the bigger pad for later use.
6. To figure out the number of big pads, see how many spaces are left after applying all lesser pads. The number of spaces left means we can replace that many number of lesser pads with big pads to fill up the group. Note that there might not be any big pads.
7. Since we will apply all big pads first, split the group in two:
   • The first word, and then `btimes` amount of words (might be none)
   • The rest of the words.
8. Join the first group together with big pads. If it’s just the first word, no big pads are added.
9. If there are “lesser” words, join them together with lesser pads, and add a lesser pad to the front.
10. Combine these two strings. The group has been padded.