LeetCode Challenge 68: Text Justification - JavaScript Solution 🚀

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:

1. Each line has exactly maxWidth characters.
2. Lines are fully justified (left and right aligned).
3. 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

1. 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.

2. 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.

3. 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

1. Discuss Edge Cases:

   • Single word input (["word"]).
   • Long words exceeding maxWidth.
   • Words perfectly filling the width.

2. Explain Spacing Logic:

   • Distribute spaces evenly across words.
   • Handle leftover spaces by adding them to the left.

3. Follow Constraints:

   • Ensure all lines are exactly maxWidth characters.

---

📚 Learn More

Check out the detailed explanation and code walkthrough on my Dev.to post:
👉 Find the Index of the First Occurrence in a String - JavaScript Solution

How do you handle string manipulation challenges? Let’s discuss! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!