Minimum Lines for Text Wrapping

Overview

The problem asks us to determine the minimum number of lines required to fit a sequence of words within a fixed maxWidth. This is a classic greedy problem. The core intuition is that to minimize the total number of lines, we should pack as many words as possible into the current line before moving to the next.

Crucially, the problem specifies that:

1. Words are separated by exactly one space on a line.
2. If a single word exceeds the maxWidth, it occupies its own line entirely.
3. Extra spaces in the input should be ignored (we only care about the words themselves).

Brute Force

A "brute force" approach in this context is similar to the optimal one because the problem naturally follows a linear progression. We can split the string into a list of words, then try every possible combination of word groupings to find the minimum lines. However, since the order of words is fixed, the "greedy" choice of filling each line as much as possible is actually globally optimal.

A less efficient version might involve building the actual strings for every line and checking their lengths repeatedly.

def min_lines_to_wrap(text: str, maxWidth: int) -> int:
    # Handle empty or whitespace-only strings
    words = text.split()
    if not words:
        return 0
    
    lines = []
    current_line_words = []
    
    for word in words:
        # Calculate length if we were to add this word to the current line
        # Length = existing words + existing spaces + new word
        current_len = sum(len(w) for w in current_line_words) + len(current_line_words) + len(word)
        
        if not current_line_words:
            current_line_words.append(word)
        elif current_len <= maxWidth:
            current_line_words.append(word)
        else:
            # Current word doesn't fit, finalize current line and start new one
            lines.append(" ".join(current_line_words))
            current_line_words = [word]
            
    if current_line_words:
        lines.append(" ".join(current_line_words))
        
    return len(lines)

Time complexity: O(N * K) — Where N is the number of words and K is the average number of words per line, due to repeated summing of word lengths and string joining. Space complexity: O(N) — Storing all words and the list of formatted line strings.

Optimal / Best Approach

The optimal approach uses the Greedy Strategy. Instead of building strings or re-summing lengths, we maintain a running count of the current line's width.

1. Split the input text into words to normalize spaces.
2. Initialize line_count = 1 (if words exist) and current_width = 0.
3. For each word:
   • If it's the first word on a line, its length is len(word).
   • If it's not the first, its contribution is 1 (for the space) + len(word).
   • If adding the word exceeds maxWidth, increment line_count and reset current_width to the word's length.

def min_lines_to_wrap(text: str, maxWidth: int) -> int:
    # Split handles multiple spaces and leading/trailing whitespace automatically
    words = text.split()
    
    if not words:
        return 0
    
    line_count = 1
    # Initialize with the length of the first word
    current_line_width = len(words[0])
    
    for i in range(1, len(words)):
        word = words[i]
        word_len = len(word)
        
        # Check if adding (1 space + word) fits in the current line
        if current_line_width + 1 + word_len <= maxWidth:
            current_line_width += 1 + word_len
        else:
            # Word must go on a new line
            line_count += 1
            current_line_width = word_len
            
    return line_count

Time complexity: O(N) — We iterate through the input string once to split it and once through the list of words. Space complexity: O(N) — In the worst case (many short words), the words list stores the entire content of the string.

Edge Cases

• Empty String: text = "" should return 0. The .split() method returns an empty list, and our check handles it.
• Single Word > maxWidth: The problem states the word is placed alone on its own line even if it overflows. Our logic handles this because current_line_width is simply set to word_len, and the next word will inevitably trigger a new line because word_len + 1 + next_word_len will certainly be > maxWidth.
• Multiple Spaces: Using text.split() ensures that "hello world" is treated exactly like "hello world".
• maxWidth of 1: If words are length 1, they fit. If they are longer, each word gets its own line.

Fast