DEV Community

Cover image for LeetCode Challenge 68: Text Justification - JavaScript Solution ๐Ÿš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

1 1 1 1 1

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.  "
]
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16  
Output:  
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Enter fullscreen mode Exit fullscreen mode

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                  "
]
Enter fullscreen mode Exit fullscreen mode

๐Ÿ† 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);
}
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” 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

Text Justification
Output:

[
  "This    is    an",
  "example  of text",
  "justification.  "
]
Enter fullscreen mode Exit fullscreen mode

โœจ 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

Image of Timescale

๐Ÿš€ pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applicationsโ€”without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more โ†’

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Image of Docusign

๐Ÿ› ๏ธ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more