Number of Lines To Write String

Problem Statement

You are provided with a string s composed of lowercase English letters and a corresponding array widths. This array maps each letter of the alphabet to a specific pixel width; for example, widths[0] corresponds to the width of 'a', widths[1] to the width of 'b', and so forth. The task is to simulate the process of writing this string s on multiple lines where the maximum width of each line does not exceed 100 pixels.

Begin at the start of string s and continue adding letters to the first line until adding another letter would exceed this 100-pixel limit. Subsequently, start the next line with the next letter in the sequence and repeat the process until all letters in s have been written.

The output should be an array result of two elements where result[0] represents the total number of lines used and result[1] indicates the width of the final line in pixels.

Examples

Example 1

Input:

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"

Output:

[3,60]

Explanation:

You can write s as follows:
abcdefghij // 100 pixels wide
klmnopqrst // 100 pixels wide
uvwxyz // 60 pixels wide
There are a total of 3 lines, and the last line is 60 pixels wide.

Example 2

Input:

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], s = "bbbcccdddaaa"

Output:

[2,4]

Explanation:

You can write s as follows:
bbbcccdddaa // 98 pixels wide
a // 4 pixels wide
There are a total of 2 lines, and the last line is 4 pixels wide.

Constraints

• widths.length == 26
• 2 <= widths[i] <= 10
• 1 <= s.length <= 1000
• s contains only lowercase English letters.

Approach and Intuition

Given this problem, a straightforward approach can be followed:

1. Initialize line and current width trackers — countLines set to 1, since we start with the first line, and currentWidth set to 0 for accumulating the pixel width of the current line.
2. Iterate through each character in the string s:
   • Determine the character's respective width from the widths array.
   • Check if adding this character exceeds the maximum permitted width (100 pixels):
     • If yes, increment the countLines counter (indicating a new line) and reset currentWidth to the current character's width since it starts a new line.
     • If no, simply add this character's width to currentWidth.
3. Upon exiting the loop, the number of lines and the width of the last line you ended up with will be the required values to be returned.
4. Compile these values into an array [countLines, currentWidth] and return it.

The crux of the algorithm revolves around sequentially processing each character, checking constraints and adjusting counters and accumulators accordingly. This approach ensures that the implementation is both efficient and straightforward, complying well within the given constraints. The simplicity of operations within the loop (simple arithmetic and conditional checks) allows the algorithm to run efficiently even for the upper limits of the input size.

Solutions

class Solution {
    public int[] computeLineMetrics(int[] charWidths, String content) {
        int totalLines = 1;
        int currentLineWidth = 0;
        for (char ch: content.toCharArray()) {
            int charWidth = charWidths[ch - 'a'];
            currentLineWidth += charWidth;
            if (currentLineWidth > 100) {
                totalLines++;
                currentLineWidth = charWidth;
            }
        }
    
        return new int[]{totalLines, currentLineWidth};
    }
}