#806

Easy

LeetCode Problem Workspace

Number of Lines To Write String

Calculate how many lines are needed to write a string given individual letter widths, constrained to 100 pixels per line.

array string

Problem Statement

You are given a string of lowercase English letters and an array widths where widths[i] represents the pixel width of the letter corresponding to index i ('a' is 0, 'b' is 1, etc.). Your task is to write the string across multiple lines without exceeding 100 pixels per line. Each line should contain as many letters as possible before reaching the pixel limit.

Return an array of length 2 where the first element is the total number of lines needed, and the second element is the width of the last line in pixels. For example, with widths = [10,...,10] and s = "abcdefghijklmnopqrstuvwxyz", the output should be [3,60].

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]

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]

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.

Solution Approach

Iterate and Accumulate Widths

Loop through each character in the string, convert it to the corresponding index in the widths array, and add its width to a current line total. If the line total exceeds 100, increment the line counter and set the current width to the character's width. This approach directly aligns with the 'Array plus String' pattern by mapping each character to a width and tracking accumulation.

Track Line Count and Last Line Width

Maintain two variables: totalLines initialized to 1 and currentWidth initialized to 0. Every time a character addition would exceed 100 pixels, increment totalLines and reset currentWidth to that character's width. After processing all characters, the currentWidth gives the width of the last line.

Edge Case Handling

Ensure you handle cases where a character exactly reaches 100 pixels, and avoid off-by-one errors when the last line is empty or partially filled. This is crucial to prevent incorrect line counts or last line width values, which is a common failure mode in this specific problem pattern.

Complexity Analysis

Metric	Value
Time	O(S\text{
Space	O(1)

The solution iterates through each character once, so the time complexity is O(N) where N is the length of the string. Only a few counters are used, so the space complexity is O(1).

What Interviewers Usually Probe

Look for clear handling of line overflow when character width exceeds remaining space.
Check if you accurately map letters to widths using the array index.
Expect attention to edge cases where the last line may not reach the full 100 pixels.

Common Pitfalls or Variants

Common pitfalls

Off-by-one errors when a character exactly fills the line.
Incorrectly resetting current width after line increment.
Assuming all letters have equal width and ignoring the widths array.

Follow-up variants

Allow variable maximum line width instead of fixed 100 pixels.
Return the pixel widths of all lines instead of just the last line.
Handle strings that include uppercase letters or special characters with defined widths.

FAQ

What is the best approach for Number of Lines To Write String?

Iterate through the string, accumulate widths from the array, and increment the line count whenever the 100-pixel limit is exceeded.

How do I handle characters that exactly reach 100 pixels?

When adding a character hits 100 pixels exactly, count it on the current line and start a new line with the next character.

Can the widths array contain values other than 2-10?

Constraints specify 2 <= widths[i] <= 10, so all characters will have widths within this range, simplifying accumulation logic.

Is the solution time complexity linear?

Yes, iterating through the string once gives O(N) time complexity and O(1) space since only counters are used.

Does this problem represent the Array plus String pattern?

Yes, it combines array lookups with sequential string processing to manage line widths, which is a classic Array plus String pattern.

terminal

Solution

Solution 1: Simulation

We define two variables `lines` and `last`, representing the number of lines and the width of the last line, respectively. Initially, `lines = 1` and `last = 0`.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        lines, last = 1, 0
        for w in map(lambda c: widths[ord(c) - ord("a")], s):
            if last + w <= 100:
                last += w
            else:
                lines += 1
                last = w
        return [lines, last]

Continue Practicing

#804 unique morse code words #809 expressive words #811 subdomain visit count