Problem Description

You are given an array widths of length 26, where widths[i] represents the width of the lowercase English letter chr(i + ord('a')). You are also given a string S.

You need to write the string S on lines such that each line can contain at most 100 units of width. You must write characters in order, and you cannot split a character between lines.

Return an array or list containing two integers:

• The total number of lines needed to write the string.
• The width used by the last line.

• Each character's width is between 2 and 10.
• Each character in S is a lowercase letter.
• There is only one valid way to split the string into lines given the widths.

Thought Process

At first glance, the problem seems to ask for a simple simulation: write the string character by character, keeping track of the current line's width, and starting a new line whenever adding the next character would exceed the maximum width (100 units).

The brute-force approach would be to scan through the string, for each character:

• Check if adding it to the current line would exceed 100 units.
• If so, start a new line and reset the current width.
• Otherwise, add the character's width to the current line's total.

Solution Approach

Let's break down the algorithm step-by-step:

1. Initialize counters: Start with lines = 1 (since at least one line is needed) and curr_width = 0 to track the width used on the current line.
2. Iterate through each character in S:
   • For each character, determine its width using the widths array. For example, widths[ord(char) - ord('a')].
   • If curr_width + char_width > 100, increment lines and reset curr_width to the current character's width (since it starts the new line).
   • Otherwise, add char_width to curr_width.
3. Return the result: After processing all characters, return [lines, curr_width], where curr_width is the width used on the last line.

This approach is efficient and simple because:

• We only need a single pass through the string (O(n) time).
• We use constant space for counters.

Example Walkthrough

Example:
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]
S = "abcdefghijklmnopqrstuvwxyz"

Let's trace the process:

• Each letter has width 10.
• Each line can hold 100 units, so 10 letters per line.
• The first 10 letters ('a' to 'j') fit on line 1 (width = 100).
• Next 10 letters ('k' to 't') fit on line 2 (width = 100).
• Last 6 letters ('u' to 'z') fit on line 3 (width = 60).

Time and Space Complexity

Brute-force approach:
Even the brute-force approach here is efficient, since we process each character once.

• Time Complexity: O(n), where n is the length of S.
• Space Complexity: O(1), only a few variables are used for tracking lines and width.

Summary

This problem is a straightforward simulation: write out the string character by character, keeping track of the current line's width and moving to a new line as needed. The key insight is to process each character in order, using a simple counter for the line width and number of lines. This makes for an elegant, efficient, and easy-to-understand solution.

Code Implementation

class Solution:
    def numberOfLines(self, widths, S):
        lines = 1
        curr_width = 0
        for c in S:
            w = widths[ord(c) - ord('a')]
            if curr_width + w > 100:
                lines += 1
                curr_width = w
            else:
                curr_width += w
        return [lines, curr_width]
      

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string S) {
        int lines = 1, curr_width = 0;
        for (char c : S) {
            int w = widths[c - 'a'];
            if (curr_width + w > 100) {
                lines++;
                curr_width = w;
            } else {
                curr_width += w;
            }
        }
        return {lines, curr_width};
    }
};
      

class Solution {
    public int[] numberOfLines(int[] widths, String S) {
        int lines = 1, curr_width = 0;
        for (char c : S.toCharArray()) {
            int w = widths[c - 'a'];
            if (curr_width + w > 100) {
                lines++;
                curr_width = w;
            } else {
                curr_width += w;
            }
        }
        return new int[]{lines, curr_width};
    }
}
      

var numberOfLines = function(widths, S) {
    let lines = 1, curr_width = 0;
    for (let i = 0; i < S.length; ++i) {
        let w = widths[S.charCodeAt(i) - 'a'.charCodeAt(0)];
        if (curr_width + w > 100) {
            lines++;
            curr_width = w;
        } else {
            curr_width += w;
        }
    }
    return [lines, curr_width];
};