68. Text Justification

Problem Description

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Examples

Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output: [
   "This    is    an",
   "example  of text",
   "justification.  "
]

Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output: [
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]

def fullJustify(words: List[str], maxWidth: int) -> List[str]:
    result = []
    current_line = []
    current_width = 0
    i = 0
    
    while i < len(words):
        # Check if we can add the current word
        if current_width + len(current_line) + len(words[i]) <= maxWidth:
            current_line.append(words[i])
            current_width += len(words[i])
            i += 1
        else:
            # Justify current line
            spaces_needed = maxWidth - current_width
            if len(current_line) == 1:
                # Single word case
                result.append(current_line[0] + ' ' * spaces_needed)
            else:
                # Multiple words case
                spaces_between = spaces_needed // (len(current_line) - 1)
                extra_spaces = spaces_needed % (len(current_line) - 1)
                line = ''
                for j in range(len(current_line) - 1):
                    line += current_line[j]
                    line += ' ' * spaces_between
                    if j < extra_spaces:
                        line += ' '
                line += current_line[-1]
                result.append(line)
            current_line = []
            current_width = 0
    
    # Handle last line (left-justified)
    if current_line:
        last_line = ' '.join(current_line)
        last_line += ' ' * (maxWidth - len(last_line))
        result.append(last_line)
    
    return result

class Solution {
    public List fullJustify(String[] words, int maxWidth) {
        List result = new ArrayList<>();
        List currentLine = new ArrayList<>();
        int currentWidth = 0;
        int i = 0;
        
        while (i < words.length) {
            // Check if we can add the current word
            if (currentWidth + currentLine.size() + words[i].length() <= maxWidth) {
                currentLine.add(words[i]);
                currentWidth += words[i].length();
                i++;
            } else {
                // Justify current line
                int spacesNeeded = maxWidth - currentWidth;
                if (currentLine.size() == 1) {
                    // Single word case
                    result.add(currentLine.get(0) + " ".repeat(spacesNeeded));
                } else {
                    // Multiple words case
                    int spacesBetween = spacesNeeded / (currentLine.size() - 1);
                    int extraSpaces = spacesNeeded % (currentLine.size() - 1);
                    StringBuilder line = new StringBuilder();
                    for (int j = 0; j < currentLine.size() - 1; j++) {
                        line.append(currentLine.get(j));
                        line.append(" ".repeat(spacesBetween));
                        if (j < extraSpaces) {
                            line.append(" ");
                        }
                    }
                    line.append(currentLine.get(currentLine.size() - 1));
                    result.add(line.toString());
                }
                currentLine.clear();
                currentWidth = 0;
            }
        }
        
        // Handle last line (left-justified)
        if (!currentLine.isEmpty()) {
            String lastLine = String.join(" ", currentLine);
            lastLine += " ".repeat(maxWidth - lastLine.length());
            result.add(lastLine);
        }
        
        return result;
    }
}

class Solution {
public:
    vector fullJustify(vector& words, int maxWidth) {
        vector result;
        vector currentLine;
        int currentWidth = 0;
        int i = 0;
        
        while (i < words.size()) {
            // Check if we can add the current word
            if (currentWidth + currentLine.size() + words[i].length() <= maxWidth) {
                currentLine.push_back(words[i]);
                currentWidth += words[i].length();
                i++;
            } else {
                // Justify current line
                int spacesNeeded = maxWidth - currentWidth;
                if (currentLine.size() == 1) {
                    // Single word case
                    result.push_back(currentLine[0] + string(spacesNeeded, ' '));
                } else {
                    // Multiple words case
                    int spacesBetween = spacesNeeded / (currentLine.size() - 1);
                    int extraSpaces = spacesNeeded % (currentLine.size() - 1);
                    string line;
                    for (int j = 0; j < currentLine.size() - 1; j++) {
                        line += currentLine[j];
                        line += string(spacesBetween, ' ');
                        if (j < extraSpaces) {
                            line += " ";
                        }
                    }
                    line += currentLine.back();
                    result.push_back(line);
                }
                currentLine.clear();
                currentWidth = 0;
            }
        }
        
        // Handle last line (left-justified)
        if (!currentLine.empty()) {
            string lastLine = currentLine[0];
            for (int j = 1; j < currentLine.size(); j++) {
                lastLine += " " + currentLine[j];
            }
            lastLine += string(maxWidth - lastLine.length(), ' ');
            result.push_back(lastLine);
        }
        
        return result;
    }
};

/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
var fullJustify = function(words, maxWidth) {
    const result = [];
    let currentLine = [];
    let currentWidth = 0;
    let i = 0;
    
    while (i < words.length) {
        // Check if we can add the current word
        if (currentWidth + currentLine.length + words[i].length <= maxWidth) {
            currentLine.push(words[i]);
            currentWidth += words[i].length;
            i++;
        } else {
            // Justify current line
            const spacesNeeded = maxWidth - currentWidth;
            if (currentLine.length === 1) {
                // Single word case
                result.push(currentLine[0] + ' '.repeat(spacesNeeded));
            } else {
                // Multiple words case
                const spacesBetween = Math.floor(spacesNeeded / (currentLine.length - 1));
                const extraSpaces = spacesNeeded % (currentLine.length - 1);
                let line = '';
                for (let j = 0; j < currentLine.length - 1; j++) {
                    line += currentLine[j];
                    line += ' '.repeat(spacesBetween);
                    if (j < extraSpaces) {
                        line += ' ';
                    }
                }
                line += currentLine[currentLine.length - 1];
                result.push(line);
            }
            currentLine = [];
            currentWidth = 0;
        }
    }
    
    // Handle last line (left-justified)
    if (currentLine.length > 0) {
        let lastLine = currentLine.join(' ');
        lastLine += ' '.repeat(maxWidth - lastLine.length);
        result.push(lastLine);
    }
    
    return result;
};

public class Solution {
    public IList FullJustify(string[] words, int maxWidth) {
        IList result = new List();
        List currentLine = new List();
        int currentWidth = 0;
        int i = 0;
        
        while (i < words.Length) {
            // Check if we can add the current word
            if (currentWidth + currentLine.Count + words[i].Length <= maxWidth) {
                currentLine.Add(words[i]);
                currentWidth += words[i].Length;
                i++;
            } else {
                // Justify current line
                int spacesNeeded = maxWidth - currentWidth;
                if (currentLine.Count == 1) {
                    // Single word case
                    result.Add(currentLine[0] + new string(' ', spacesNeeded));
                } else {
                    // Multiple words case
                    int spacesBetween = spacesNeeded / (currentLine.Count - 1);
                    int extraSpaces = spacesNeeded % (currentLine.Count - 1);
                    StringBuilder line = new StringBuilder();
                    for (int j = 0; j < currentLine.Count - 1; j++) {
                        line.Append(currentLine[j]);
                        line.Append(new string(' ', spacesBetween));
                        if (j < extraSpaces) {
                            line.Append(' ');
                        }
                    }
                    line.Append(currentLine[currentLine.Count - 1]);
                    result.Add(line.ToString());
                }
                currentLine.Clear();
                currentWidth = 0;
            }
        }
        
        // Handle last line (left-justified)
        if (currentLine.Count > 0) {
            string lastLine = string.Join(" ", currentLine);
            lastLine += new string(' ', maxWidth - lastLine.Length);
            result.Add(lastLine);
        }
        
        return result;
    }
}