Fully Justify Text Within a Width

hard string greedy

Problem

Given a list of words and a target line width, format the text so each line is exactly that wide. Greedily pack words into a line as long as they (with one space between each) still fit. For inner lines, redistribute the leftover spaces across the gaps — leftmost gaps absorb any remainder. The last line is left-justified with single spaces and padded on the right.

Inputwords = ["This","is","an","example"], maxWidth = 14

Output["This is an", "example "]

First line packs three words; gaps absorb 4 leftover spaces (2 + 2). Last line left-justified.

words (comma-separated)

maxWidth

def full_justify(words, W):
    out = []
    i = 0
    while i < len(words):
        length = len(words[i])
        j = i + 1
        while j < len(words) and length + 1 + len(words[j]) <= W:
            length += 1 + len(words[j])
            j += 1
        gaps = j - i - 1
        if j == len(words) or gaps == 0:
            line = " ".join(words[i:j])
            line += " " * (W - len(line))
        else:
            total_chars = sum(len(w) for w in words[i:j])
            total_spaces = W - total_chars
            base = total_spaces // gaps
            extra = total_spaces % gaps
            parts = []
            for k in range(i, j):
                parts.append(words[k])
                if k < j - 1:
                    parts.append(" " * (base + (1 if k - i < extra else 0)))
            line = "".join(parts)
        out.append(line)
        i = j
    return out

function fullJustify(words, W) {
  const out = [];
  let i = 0;
  while (i < words.length) {
    let len = words[i].length, j = i + 1;
    while (j < words.length && len + 1 + words[j].length <= W) {
      len += 1 + words[j].length;
      j++;
    }
    const gaps = j - i - 1;
    let line;
    if (j === words.length || gaps === 0) {
      line = words.slice(i, j).join(" ");
      line += " ".repeat(W - line.length);
    } else {
      const totalChars = words.slice(i, j).reduce((s, w) => s + w.length, 0);
      const totalSpaces = W - totalChars;
      const base = Math.floor(totalSpaces / gaps);
      const extra = totalSpaces % gaps;
      line = "";
      for (let k = i; k < j; k++) {
        line += words[k];
        if (k < j - 1) {
          line += " ".repeat(base + (k - i < extra ? 1 : 0));
        }
      }
    }
    out.push(line);
    i = j;
  }
  return out;
}

class Solution {
    public List<String> fullJustify(String[] words, int W) {
        List<String> out = new ArrayList<>();
        int i = 0;
        while (i < words.length) {
            int len = words[i].length(), j = i + 1;
            while (j < words.length && len + 1 + words[j].length() <= W) {
                len += 1 + words[j].length(); j++;
            }
            int gaps = j - i - 1;
            StringBuilder line = new StringBuilder();
            if (j == words.length || gaps == 0) {
                for (int k = i; k < j; k++) {
                    if (k > i) line.append(' ');
                    line.append(words[k]);
                }
                while (line.length() < W) line.append(' ');
            } else {
                int totalChars = 0;
                for (int k = i; k < j; k++) totalChars += words[k].length();
                int totalSpaces = W - totalChars;
                int base = totalSpaces / gaps, extra = totalSpaces % gaps;
                for (int k = i; k < j; k++) {
                    line.append(words[k]);
                    if (k < j - 1) {
                        int n = base + (k - i < extra ? 1 : 0);
                        for (int s = 0; s < n; s++) line.append(' ');
                    }
                }
            }
            out.add(line.toString());
            i = j;
        }
        return out;
    }
}

vector<string> fullJustify(vector<string>& words, int W) {
    vector<string> out;
    int i = 0;
    while (i < (int)words.size()) {
        int len = words[i].size(), j = i + 1;
        while (j < (int)words.size() && len + 1 + (int)words[j].size() <= W) {
            len += 1 + words[j].size(); j++;
        }
        int gaps = j - i - 1;
        string line;
        if (j == (int)words.size() || gaps == 0) {
            for (int k = i; k < j; k++) {
                if (k > i) line += ' ';
                line += words[k];
            }
            line += string(W - line.size(), ' ');
        } else {
            int totalChars = 0;
            for (int k = i; k < j; k++) totalChars += words[k].size();
            int totalSpaces = W - totalChars;
            int base = totalSpaces / gaps, extra = totalSpaces % gaps;
            for (int k = i; k < j; k++) {
                line += words[k];
                if (k < j - 1) line += string(base + (k - i < extra ? 1 : 0), ' ');
            }
        }
        out.push_back(line);
        i = j;
    }
    return out;
}

Time: O(total characters) Space: O(total characters)