Text Justification solution and explanation

def fullJustify(words, maxWidth):
    def justify_line(line, width, maxWidth):
        if len(line) == 1:
            return line[0] + ' ' * (maxWidth - width)
        total_spaces = maxWidth - width + len(line) - 1
        space, extra = divmod(total_spaces, len(line) - 1)
        for i in range(extra):
            line[i] += ' '
        return (' ' * space).join(line)

    res, line, width = [], [], 0
    for word in words:
        if width + len(word) + len(line) > maxWidth:
            res.append(justify_line(line, width, maxWidth))
            line, width = [], 0
        line.append(word)
        width += len(word)

    last_line = ' '.join(line)
    res.append(last_line + ' ' * (maxWidth - len(last_line)))
    return res

import java.util.*;

public class TextJustification {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int index = 0;
        while (index < words.length) {
            int totalChars = words[index].length();
            int last = index + 1;
            while (last < words.length) {
                if (totalChars + words[last].length() + 1 > maxWidth) break;
                totalChars += words[last].length() + 1;
                last++;
            }

            StringBuilder sb = new StringBuilder();
            int diff = last - index - 1;
            // if last line or number of words in the line is 1, left-justify
            if (last == words.length || diff == 0) {
                for (int i = index; i < last; i++) {
                    sb.append(words[i]).append(" ");
                }
                sb.deleteCharAt(sb.length() - 1);
                while (sb.length() < maxWidth) {
                    sb.append(" ");
                }
            } else {
                int spaces = (maxWidth - totalChars) / diff;
                int remainder = (maxWidth - totalChars) % diff;
                for (int i = index; i < last - 1; i++) {
                    sb.append(words[i]).append(" ");
                    for (int j = 0; j < spaces + (i - index < remainder ? 1 : 0); j++) {
                        sb.append(" ");
                    }
                }
                sb.append(words[last - 1]);
            }
            result.add(sb.toString());
            index = last;
        }
        return result;
    }
}

function fullJustify(words, maxWidth) {
    const result = [];
    let idx = 0;
    const justify = (line, maxWidth, isLastLine) => {
        if (line.length === 1) return line[0].padEnd(maxWidth);
        if (isLastLine) return line.join(' ').padEnd(maxWidth);
        const totalSpace = maxWidth - line.join('').length;
        const gaps = line.length - 1;
        const spaceBetween = Math.floor(totalSpace / gaps);
        const extraSpaces = totalSpace % gaps;
        return line.reduce((acc, word, i) => {
            if (i === gaps) return acc + word;
            return acc + word + ' '.repeat(spaceBetween + (i < extraSpaces ? 1 : 0));
        }, '');
    };

    while (idx < words.length) {
        let line = [];
        let lineLength = 0;
        while (idx < words.length && lineLength + words[idx].length + line.length <= maxWidth) {
            lineLength += words[idx].length;
            line.push(words[idx++]);
        }
        result.push(justify(line, maxWidth, idx === words.length));
    }
    return result;
}

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    int n = words.size();
    vector<int> dp(n + 1, INT_MAX);
    vector<int> path(n);
    dp[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        int len = -1;
        for (int j = i; j < n; ++j) {
            len += words[j].length() + 1;
            if (len > maxWidth) break;
            int last_cost = j == n - 1 ? 0 : maxWidth - len;
            if (dp[i] > last_cost + dp[j + 1]) {
                dp[i] = last_cost + dp[j + 1];
                path[i] = j + 1;
            }
        }
    }
    
    vector<string> res;
    for (int i = 0; i < n; i = path[i]) {
        int j = path[i];
        string line = words[i];
        for (int k = i + 1; k < j; ++k) {
            line += " " + words[k];
        }
        line += string(maxWidth - line.length(), ' ');
        res.push_back(line);
    }
    return res;
}

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    public IList<string> FullJustify(string[] words, int maxWidth) {
        int n = words.Length;
        int[] dp = new int[n + 1];
        int[] path = new int[n];
        Array.Fill(dp, int.MaxValue);
        dp[n] = 0;

        for (int i = n - 1; i >= 0; i--) {
            int lineLength = -1;
            for (int j = i; j < n && lineLength <= maxWidth; j++) {
                lineLength += words[j].Length + 1;

                if (lineLength - 1 <= maxWidth) {
                    int lastCost = j == n - 1 ? 0 : maxWidth - (lineLength - 1);

                    if (dp[i] > dp[j + 1] + lastCost) {
                        dp[i] = dp[j + 1] + lastCost;
                        path[i] = j + 1;
                    }
                }
            }
        }

        List<string> result = new List<string>();
        int k = 0;

        while (k < words.Length) {
            int end = path[k];
            StringBuilder line = new StringBuilder(words[k]);

            for (int i = k + 1; i < end; i++) {
                line.Append(' ').Append(words[i]);
            }

            line.Append(new string(' ', maxWidth - line.Length));
            result.Add(line.ToString());
            k = end;
        }

        return result;
    }
}

function fullJustify(words: string[], maxWidth: number): string[] {
    const ans: string[] = [];
    for (let i = 0, n = words.length; i < n; ) {
        const t: string[] = [words[i]];
        let cnt = words[i++].length;
        while (i < n && cnt + 1 + words[i].length <= maxWidth) {
            t.push(words[i]);
            cnt += 1 + words[i++].length;
        }
        if (i === n || t.length === 1) {
            const left: string = t.join(' ');
            const right: string = ' '.repeat(maxWidth - left.length);
            ans.push(left + right);
            continue;
        }
        const spaceWidth: number = maxWidth - (cnt - t.length + 1);
        const w: number = Math.floor(spaceWidth / (t.length - 1));
        const m: number = spaceWidth % (t.length - 1);
        const row: string[] = [];
        for (let j = 0; j < t.length - 1; ++j) {
            row.push(t[j]);
            row.push(' '.repeat(w + (j < m ? 1 : 0)));
        }
        row.push(t[t.length - 1]);
        ans.push(row.join(''));
    }
    return ans;
}

func fullJustify(words []string, maxWidth int) (ans []string) {
	for i, n := 0, len(words); i < n; {
		t := []string{words[i]}
		cnt := len(words[i])
		i++
		for i < n && cnt+1+len(words[i]) <= maxWidth {
			cnt += 1 + len(words[i])
			t = append(t, words[i])
			i++
		}
		if i == n || len(t) == 1 {
			left := strings.Join(t, " ")
			right := strings.Repeat(" ", maxWidth-len(left))
			ans = append(ans, left+right)
			continue
		}
		spaceWidth := maxWidth - (cnt - len(t) + 1)
		w := spaceWidth / (len(t) - 1)
		m := spaceWidth % (len(t) - 1)
		row := strings.Builder{}
		for j, s := range t[:len(t)-1] {
			row.WriteString(s)
			row.WriteString(strings.Repeat(" ", w))
			if j < m {
				row.WriteString(" ")
			}
		}
		row.WriteString(t[len(t)-1])
		ans = append(ans, row.String())
	}
	return
}