Sentence Boxing

The "Sentence Boxing" problem focuses on basic string manipulation, formatting, and standard output construction. It tests your ability to calculate layout dimensions and apply padding consistently across multiple elements.

Overview

The core challenge is to determine a uniform width for multiple independent "boxes." Since the box width depends on the longest string in the input list, we must process the input in two distinct phases:

1. Measurement: Find the maximum length among all strings to set the internal width.
2. Construction: Iterate through the strings and build the ASCII borders and padded content lines.

Brute Force

A brute force approach in this context is essentially a direct implementation of the rules. We iterate through the list once to find the maximum length, then iterate again to build every single line required. Since we are building the strings manually using concatenation or basic multiplication, it is straightforward.

def sentence_boxing(sentences: list[str]) -> list[str]:
    if not sentences:
        return []
    
    # Phase 1: Find the max length
    max_len = 0
    for s in sentences:
        if len(s) > max_len:
            max_len = len(s)
            
    result = []
    
    # Phase 2: Construct the boxes
    for s in sentences:
        # Create top/bottom border: + then max_len dashes then +
        border = "+" + ("-" * max_len) + "+"
        
        # Create the content line: | then sentence then padding then |
        padding_needed = max_len - len(s)
        content = "|" + s + (" " * padding_needed) + "|"
        
        result.append(border)
        result.append(content)
        
    # The problem requires a final closing border for the last box
    # Since boxes are separate, every sentence gets a top and bottom.
    if sentences:
        result.append("+" + ("-" * max_len) + "+")
        
    return result

Time complexity: O(N * M) — Where N is the number of sentences and M is the length of the longest sentence, as we must touch every character to build the output strings. Space complexity: O(N * M) — We store the formatted result which scales linearly with the total number of characters in the output.

Optimal Approach

The optimal approach follows the same logic as the brute force but leverages Python's built-in string methods like max() with a key function and string formatting/f-strings for cleaner, more efficient code.

Using ljust() simplifies the padding logic significantly, and we can pre-calculate the border string since it is identical for every box.

def sentence_boxing(sentences: list[str]) -> list[str]:
    if not sentences:
        return []
    
    # Use max() with a key to find the longest length efficiently
    max_w = len(max(sentences, key=len))
    
    # Pre-calculate the horizontal border
    border = f"+{'-' * max_w}+"
    
    res = []
    for s in sentences:
        res.append(border)
        # ljust(max_w) pads the string with spaces to the right
        res.append(f"|{s.ljust(max_w)}|")
        
    # Append the final closing border
    res.append(border)
    
    return res

Time complexity: O(N * M) — We perform two passes: one to find the maximum length and one to construct the final list of strings. Space complexity: O(N * M) — The output list stores approximately $3N$ strings, each of length $M+2$.

Why this works

1. Uniformity: By calculating max_w first, we ensure all boxes "stack" perfectly if printed, as they all share the same width regardless of the individual sentence length.
2. Padding: The ljust method (or manually adding spaces) ensures that the right-side | border stays aligned vertically.
3. Efficiency: Even though we iterate twice, the complexity remains linear relative to the size of the input/output ($O(\text{Total Characters})$).

Edge Cases

• Single Sentence: The logic holds; max_w is simply the length of that one sentence.
• Sentences of length 1: The box will be 3 characters wide (+--+).
• Variable lengths: The shortest sentence will receive the most padding, while the longest sentence will have zero spaces between its last character and the right | border.

Fast