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