Problem #68: Text Justification

Intuition & Strategy Breakdown

Pack words greedily into lines up to maxWidth. Distribute spaces evenly between words for fully justified lines, left-justifying the final line.

Python Solution

class Solution:
    def fullJustify(self, words: list[str], maxWidth: int) -> list[str]:
        res, cur, num_of_letters = [], [], 0
        for w in words:
            if num_of_letters + len(w) + len(cur) > maxWidth:
                for i in range(maxWidth - num_of_letters):
                    cur[i % (len(cur) - 1 or 1)] += ' '
                res.append(''.join(cur))
                cur, num_of_letters = [], 0
            cur.append(w)
            num_of_letters += len(w)
        return res + [' '.join(cur).ljust(maxWidth)]

Java Solution

class Solution {
    public List fullJustify(String[] words, int maxWidth) {
        List res = new ArrayList<>();
        int i = 0;
        while (i < words.length) {
            int j = i + 1;
            int lineLen = words[i].length();
            while (j < words.length && lineLen + 1 + words[j].length() <= maxWidth) {
                lineLen += 1 + words[j].length();
                j++;
            }
            StringBuilder sb = new StringBuilder();
            int diff = j - i - 1;
            if (j == words.length || diff == 0) {
                for (int k = i; k < j; k++) {
                    sb.append(words[k]);
                    if (k < j - 1) sb.append(" ");
                }
                while (sb.length() < maxWidth) sb.append(" ");
            } else {
                int spaces = (maxWidth - lineLen) / diff;
                int r = (maxWidth - lineLen) % diff;
                for (int k = i; k < j; k++) {
                    sb.append(words[k]);
                    if (k < j - 1) {
                        for (int s = 0; s <= spaces + (k - i < r ? 1 : 0); s++) sb.append(" ");
                    }
                }
            }
            res.add(sb.toString());
            i = j;
        }
        return res;
    }
}