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

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

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!

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

πŸ‘₯ Ideal for solo developers, teams, and cross-company projects

Learn more