Problem Description

You have a string s containing only lowercase English letters and an array widths of length 26. Each element in widths represents the pixel width of the corresponding lowercase letter - widths[0] is the width of 'a', widths[1] is the width of 'b', and so on through widths[25] for 'z'.

You need to write the string s across multiple lines following these rules:

• Each line can hold a maximum of 100 pixels width
• Start writing from the beginning of s and fit as many complete letters as possible on the first line without exceeding 100 pixels
• Continue from where you left off, writing as many letters as possible on each subsequent line
• Keep going until all letters in s have been written

The task is to return an array of two integers:

1. The first element should be the total number of lines needed to write the entire string
2. The second element should be the pixel width used on the last line

For example, if you're writing a string where adding the next letter would make the current line exceed 100 pixels, you must start a new line with that letter instead.

Intuition

The problem is essentially about simulating the process of writing text with a line width constraint. Think of it like typing on an old typewriter that automatically moves to the next line when you reach the right margin.

The key insight is that we need to keep track of two things as we process each character:

1. How many lines we've used so far
2. How much space is currently used on the current line

For each character in the string, we face a simple decision: can it fit on the current line or not?

If we're currently at position last pixels on the current line and want to add a character with width w, we check if last + w <= 100. If yes, we simply add the character to the current line by updating last += w. If no, we must start a new line, which means incrementing our line counter and resetting the current line width to just the width of this character (last = w).

The process naturally simulates what happens when writing with a fixed-width constraint - we greedily fit as many characters as possible on each line before moving to the next one. Since we start with lines = 1 (we always have at least one line) and last = 0 (initially nothing is written), we can process each character sequentially and maintain these two values throughout.

The beauty of this approach is its simplicity - we don't need to look ahead or backtrack. We just process each character in order, making the immediate decision of whether it fits on the current line or requires a new one.

Solution Approach

The solution uses a simple simulation approach to solve the problem. We process each character in the string sequentially and maintain two variables to track our progress.

Variables:

• lines: Counts the total number of lines used (initialized to 1 since we always have at least one line)
• last: Tracks the current width used on the current line (initialized to 0)

Algorithm Steps:

1. Initialize the tracking variables: Start with lines = 1 and last = 0.

2. Process each character: For each character c in the string s:

   • Calculate its width: w = widths[ord(c) - ord('a')]
     • This uses ASCII values to map each character to its corresponding index in the widths array
     • For example, 'a' maps to index 0, 'b' to index 1, etc.

3. Check if the character fits on the current line:

   • If last + w <= 100: The character fits on the current line
     • Add its width to the current line: last += w
   • Otherwise: The character doesn't fit and needs a new line
     • Increment the line counter: lines += 1
     • Start the new line with just this character: last = w

4. Return the result: After processing all characters, return [lines, last]

The implementation uses Python's map function with a lambda expression to elegantly convert each character to its width: map(lambda c: widths[ord(c) - ord("a")], s). This creates an iterator that yields the width of each character as we process the string.

Time Complexity: O(n) where n is the length of string s, as we process each character exactly once.

Space Complexity: O(1) as we only use a constant amount of extra space for the two tracking variables.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Input:

• s = "abcdefghij"
• widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10] (Each letter has width 10 pixels)

Step-by-step simulation:

Initialize: lines = 1, last = 0

1. Character 'a' (width = 10):

   • Check: last + 10 = 0 + 10 = 10 ≤ 100 ✓
   • Add to current line: last = 10
   • Status: Line 1 has "a" (10 pixels used)

2. Character 'b' (width = 10):

   • Check: last + 10 = 10 + 10 = 20 ≤ 100 ✓
   • Add to current line: last = 20
   • Status: Line 1 has "ab" (20 pixels used)

3. Characters 'c' through 'j':

   • Each adds 10 more pixels to the current line
   • After 'c': last = 30 (Line 1: "abc")
   • After 'd': last = 40 (Line 1: "abcd")
   • After 'e': last = 50 (Line 1: "abcde")
   • After 'f': last = 60 (Line 1: "abcdef")
   • After 'g': last = 70 (Line 1: "abcdefg")
   • After 'h': last = 80 (Line 1: "abcdefgh")
   • After 'i': last = 90 (Line 1: "abcdefghi")
   • After 'j': last = 100 (Line 1: "abcdefghij")

Result: [1, 100] - We used 1 line with 100 pixels on the last (and only) line.

Another example with line wrapping:

Input:

• s = "bbbcccdddaa"
• widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10] (Letter 'a' has width 4, letters 'b', 'c', 'd' have width 10)

Initialize: lines = 1, last = 0

1. 'b' (width = 10): 0 + 10 ≤ 100 ✓ → last = 10
2. 'b' (width = 10): 10 + 10 ≤ 100 ✓ → last = 20
3. 'b' (width = 10): 20 + 10 ≤ 100 ✓ → last = 30
4. 'c' (width = 10): 30 + 10 ≤ 100 ✓ → last = 40
5. 'c' (width = 10): 40 + 10 ≤ 100 ✓ → last = 50
6. 'c' (width = 10): 50 + 10 ≤ 100 ✓ → last = 60
7. 'd' (width = 10): 60 + 10 ≤ 100 ✓ → last = 70
8. 'd' (width = 10): 70 + 10 ≤ 100 ✓ → last = 80
9. 'd' (width = 10): 80 + 10 ≤ 100 ✓ → last = 90
10. 'd' (width = 10): 90 + 10 ≤ 100 ✓ → last = 100
11. 'a' (width = 4): 100 + 4 = 104 > 100 ✗
    • Start new line: lines = 2, last = 4
12. 'a' (width = 4): 4 + 4 ≤ 100 ✓ → last = 8

Result: [2, 8] - We used 2 lines, with 8 pixels on the last line.

The visual representation would be:

• Line 1: "bbbcccddd" (100 pixels)
• Line 2: "aa" (8 pixels)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the algorithm iterates through each character in the string exactly once. The map function processes each character to get its corresponding width value from the widths array, and for each character, it performs constant-time operations: looking up the width value using ord(c) - ord("a") (which is O(1)), comparing last + w <= 100 (which is O(1)), and updating the lines and last variables (which are O(1) operations).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. It maintains two integer variables (lines and last) to track the current state, and the map function creates an iterator that processes elements one at a time without storing them all in memory. The space used does not grow with the size of the input string s.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Line Counting

A common mistake is incorrectly initializing the line counter or forgetting to start with at least one line. Some might initialize line_count = 0 thinking they'll increment it when adding characters, but this leads to an incorrect count.

Incorrect approach:

line_count = 0  # Wrong initialization
for char in s:
    char_width = widths[ord(char) - ord('a')]
    if current_line_width + char_width <= 100:
        current_line_width += char_width
    else:
        line_count += 1
        current_line_width = char_width
# This misses counting the first/last line properly

Solution: Always initialize line_count = 1 since you start writing on the first line immediately.

2. Incorrect Character-to-Index Mapping

Another frequent error is using the wrong formula to map characters to their width indices. Common mistakes include:

• Using ord(char) - ord('A') instead of ord(char) - ord('a') (wrong case)
• Directly using widths[char] without converting to index
• Off-by-one errors like ord(char) - ord('a') + 1

Incorrect approaches:

# Wrong: Using uppercase 'A'
char_width = widths[ord(char) - ord('A')]

# Wrong: Treating char as index directly
char_width = widths[char]

# Wrong: Adding unnecessary offset
char_width = widths[ord(char) - ord('a') + 1]

Solution: Use the correct formula: widths[ord(char) - ord('a')] where ord('a') gives the ASCII value of lowercase 'a'.

3. Resetting Line Width Incorrectly

When starting a new line, some might forget to include the current character's width or might accidentally carry over the previous line's width.

Incorrect approach:

if current_line_width + char_width > 100:
    line_count += 1
    current_line_width = 0  # Wrong: should be char_width, not 0

Solution: When starting a new line, set current_line_width = char_width to account for the character that triggered the new line.

4. Edge Case: Empty String

While not explicitly mentioned in the problem, handling an empty string could cause issues if not considered.

Solution: Add a check at the beginning:

if not s:
    return [0, 0]  # or [1, 0] depending on requirements

5. Using Wrong Comparison Operator

Using < instead of <= when checking if a character fits on the current line.

Incorrect approach:

if current_line_width + char_width < 100:  # Wrong: should be <=
    current_line_width += char_width

Solution: Use <= to allow exactly 100 pixels on a line: if current_line_width + char_width <= 100: