DSA 450 Notes

Problem Statement

Given a sequence of words and a maximum line width M, format the text such that each line has exactly M characters. Text should be fully justified (left and right aligned) with extra spaces distributed as evenly as possible. If spaces cannot be distributed evenly, extra spaces go to the left. The last line should be left-justified.

Example:

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

"This    is    an"
"example  of text"
"justification.  "

Approach 1: Greedy Line Packing

Intuition

Pack as many words as possible into each line while respecting the width constraint. Then justify each line by distributing extra spaces.

Algorithm

Greedily pack words into lines
For each line (except last):
- Calculate total spaces needed
- Distribute spaces evenly between words
- Extra spaces go to leftmost gaps
Left-justify the last line

java

import java.util.*;

public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int n = words.length;
        int i = 0;
        
        while (i < n) {
            // Find how many words fit in this line
            int lineLength = words[i].length();
            int j = i + 1;
            
            while (j < n && lineLength + 1 + words[j].length() <= maxWidth) {
                lineLength += 1 + words[j].length();
                j++;
            }
            
            // Number of words in this line
            int numWords = j - i;
            int numSpaces = numWords - 1;
            
            StringBuilder line = new StringBuilder();
            
            // Last line or single word line: left justify
            if (j == n || numWords == 1) {
                for (int k = i; k < j; k++) {
                    line.append(words[k]);
                    if (k < j - 1) line.append(" ");
                }
                // Pad with spaces
                while (line.length() < maxWidth) {
                    line.append(" ");
                }
            } else {
                // Calculate words length without spaces
                int wordsLength = 0;
                for (int k = i; k < j; k++) {
                    wordsLength += words[k].length();
                }
                
                int totalSpaces = maxWidth - wordsLength;
                int spacePerGap = totalSpaces / numSpaces;
                int extraSpaces = totalSpaces % numSpaces;
                
                for (int k = i; k < j; k++) {
                    line.append(words[k]);
                    if (k < j - 1) {
                        int spaces = spacePerGap + (k - i < extraSpaces ? 1 : 0);
                        for (int s = 0; s < spaces; s++) {
                            line.append(" ");
                        }
                    }
                }
            }
            
            result.add(line.toString());
            i = j;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × M) where n is number of words and M is max width
Space Complexity: O(n × M) for storing the result

Approach 2: Dynamic Programming (Minimum Raggedness)

Intuition

The greedy approach may not produce the most aesthetically pleasing result. DP can minimize "raggedness" - the sum of squares of extra spaces at the end of each line (called badness).

Algorithm

Define cost of putting words[i..j] in one line
dp[i] = minimum cost to arrange words[i..n-1]
Use memoization to avoid recomputation

Complexity Analysis

Time Complexity: O(n²) - For each starting position, try all ending positions
Space Complexity: O(n) - Memoization table

Key Takeaways

Greedy approach works well for most practical cases
DP approach minimizes raggedness for optimal aesthetics
Special handling needed for:
- Last line (left-justified)
- Single word lines
Extra spaces should be distributed left to right
This is a classic typesetting algorithm problem
Related to the Knuth-Plass line breaking algorithm used in TeX
The problem teaches space distribution and string formatting

Word Wrap Problem [VERY IMP]

Problem Statement

Approach 1: Greedy Line Packing

Intuition

Algorithm

Complexity Analysis

Approach 2: Dynamic Programming (Minimum Raggedness)

Intuition

Algorithm

Complexity Analysis

Key Takeaways