LeetCode Challenge 68: Text Justification - JavaScript Solution 🚀

#javascript #programming #leetcode #interview

Top Interview 150

The Text Justification problem is a great test of string manipulation and greedy algorithms. Let’s tackle LeetCode 68: Text Justification and solve it step by step.

🚀 Problem Description

Given an array of strings words and an integer maxWidth, format the text so that:

Each line has exactly maxWidth characters.
Lines are fully justified (left and right aligned).
Extra spaces are distributed as evenly as possible.
- If the number of spaces does not divide evenly, assign more spaces to the left. . The last line must be left-justified.

💡 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        "
]

Example 3

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20  
Output:  
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

🏆 JavaScript Solution

We’ll use a greedy approach to pack as many words as possible into each line, then format the lines according to the rules.

Implementation

var fullJustify = function(words, maxWidth) {
    const result = [];
    let line = [];
    let lineLength = 0;

    for (let word of words) {
        if (lineLength + word.length + line.length > maxWidth) {
            result.push(justifyLine(line, lineLength, maxWidth));
            line = [];
            lineLength = 0;
        }

        line.push(word);
        lineLength += word.length;
    }

    result.push(leftJustifyLine(line, maxWidth));
    return result;
};

function justifyLine(line, lineLength, maxWidth) {
    const spacesNeeded = maxWidth - lineLength;
    const gaps = line.length - 1;

    if (gaps === 0) {
        return line[0] + ' '.repeat(spacesNeeded);
    }

    const spacePerGap = Math.floor(spacesNeeded / gaps);
    const extraSpaces = spacesNeeded % gaps;

    let justified = '';
    for (let i = 0; i < line.length - 1; i++) {
        justified += line[i] + ' '.repeat(spacePerGap + (i < extraSpaces ? 1 : 0));
    }
    justified += line[line.length - 1]; // Add the last word
    return justified;
}

function leftJustifyLine(line, maxWidth) {
    return line.join(' ') + ' '.repeat(maxWidth - line.join(' ').length);
}

🔍 How It Works

Greedy Line Packing:
- Add words to the current line until adding another word exceeds maxWidth.
- Once the limit is reached, justify the current line and start a new one.
Justify Each Line:
- Middle Justification: Distribute spaces evenly across words, giving extra spaces to the left when needed.
- Left Justification (for the last line): Add spaces only at the end.
Output:
- Append the justified lines to the result.

🔑 Complexity Analysis

Time Complexity: O(n), where n is the total number of characters in the input.
- Each word is processed once.
- Space calculations and string manipulations take O(1) per word.
Space Complexity: O(n), for the output array of lines.

📋 Dry Run

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

Output:

[
  "This    is    an",
  "example  of text",
  "justification.  "
]

✨ Pro Tips for Interviews

Discuss Edge Cases:
- Single word input (["word"]).
- Long words exceeding maxWidth.
- Words perfectly filling the width.
Explain Spacing Logic:
- Distribute spaces evenly across words.
- Handle leftover spaces by adding them to the left.
Follow Constraints:
- Ensure all lines are exactly maxWidth characters.