Text Justification

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

import "strings"

func fullJustify(words []string, maxWidth int) []string {
  var ans []string
  n := len(words)
  i := 0
  for i < n {
    j, length := i, 0
    for j < n && length+len(words[j])+(j-i) <= maxWidth {
      length += len(words[j])
      j++
    }
    gaps := j - i - 1
    var line strings.Builder
    if gaps == 0 || j == n {
      for k := i; k < j; k++ {
        line.WriteString(words[k])
        if k+1 < j {
          line.WriteByte(' ')
        }
      }
      line.WriteString(strings.Repeat(" ", maxWidth-line.Len()))
    } else {
      totalSpaces := maxWidth - length
      base, extra := totalSpaces/gaps, totalSpaces%gaps
      for k := i; k < j; k++ {
        line.WriteString(words[k])
        if k+1 < j {
          sp := base
          if k-i < extra {
            sp++
          }
          line.WriteString(strings.Repeat(" ", sp))
        }
      }
    }
    ans = append(ans, line.String())
    i = j
  }
  return ans
}

from typing import List

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        ans: List[str] = []
        n = len(words)
        i = 0
        while i < n:
            j = i
            length = 0
            while j < n and length + len(words[j]) + (j - i) <= maxWidth:
                length += len(words[j])
                j += 1
            gaps = j - i - 1
            if gaps == 0 or j == n:
                line = ' '.join(words[i:j])
                line += ' ' * (maxWidth - len(line))
            else:
                total_spaces = maxWidth - length
                base, extra = divmod(total_spaces, gaps)
                parts: List[str] = []
                for k in range(i, j):
                    parts.append(words[k])
                    if k + 1 < j:
                        sp = base + (1 if k - i < extra else 0)
                        parts.append(' ' * sp)
                line = ''.join(parts)
            ans.append(line)
            i = j
        return ans

var fullJustify = function(words, maxWidth) {
    const ans = [];
    const n = words.length;
    let i = 0;
    while (i < n) {
        let j = i, length = 0;
        while (j < n && length + words[j].length + (j - i) <= maxWidth) {
            length += words[j].length;
            j++;
        }
        const gaps = j - i - 1;
        let line;
        if (gaps === 0 || j === n) {
            line = words.slice(i, j).join(' ');
            line += ' '.repeat(maxWidth - line.length);
        } else {
            const totalSpaces = maxWidth - length;
            const base = Math.floor(totalSpaces / gaps);
            const extra = totalSpaces % gaps;
            const parts = [];
            for (let k = i; k < j; k++) {
                parts.push(words[k]);
                if (k + 1 < j) {
                    const sp = base + (k - i < extra ? 1 : 0);
                    parts.push(' '.repeat(sp));
                }
            }
            line = parts.join('');
        }
        ans.push(line);
        i = j;
    }
    return ans;
};

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

function fullJustify(words: string[], maxWidth: number): string[] {
    const ans: string[] = [];
    const n: number = words.length;
    let i: number = 0;
    while (i < n) {
        let j: number = i, length: number = 0;
        while (j < n && length + words[j].length + (j - i) <= maxWidth) {
            length += words[j].length;
            j++;
        }
        const gaps: number = j - i - 1;
        let line: string;
        if (gaps === 0 || j === n) {
            line = words.slice(i, j).join(' ');
            line += ' '.repeat(maxWidth - line.length);
        } else {
            const totalSpaces: number = maxWidth - length;
            const base: number = Math.floor(totalSpaces / gaps);
            const extra: number = totalSpaces % gaps;
            const parts: string[] = [];
            for (let k = i; k < j; k++) {
                parts.push(words[k]);
                if (k + 1 < j) {
                    const sp: number = base + (k - i < extra ? 1 : 0);
                    parts.push(' '.repeat(sp));
                }
            }
            line = parts.join('');
        }
        ans.push(line);
        i = j;
    }
    return ans;
}