Number of Lines To Write String

Difficulty: Easy | Acceptance: 72.50% | Paid: No Topics: Array, String

You are given an array of integers widths of length 26, where widths[i] represents the width of the character chr(‘a’ + i). You are also given a string s.

Write the string s across the lines of a page such that each line can hold at most 100 units. If writing a character would cause the total width of the line to exceed 100 units, you write the character on the next line instead.

Return an array of length 2 where:

• result[0] is the number of lines used

• result[1] is the width of the last line in units

• Examples

• Constraints

• Simple Iteration

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:
Each character has a width of 10.
Line 1: abcdefghij (10 characters × 10 = 100 units)
Line 2: klmnopqrst (10 characters × 10 = 100 units)
Line 3: uvwxyz (6 characters × 10 = 60 units)
Total lines: 3, Last line width: 60

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:
a = 4, b = 10, c = 10, d = 10
Line 1: bbbcccdddaa = 98 units (b×3 + c×3 + d×3 + a×2 = 30 + 30 + 30 + 8 = 98)
Line 2: a = 4 units
Total lines: 2, Last line width: 4

Constraints

- widths.length == 26
- 2 <= widths[i] <= 10
- 1 <= s.length <= 1000
- s consists of lowercase English letters.

Simple Iteration

Intuition Iterate through each character, accumulate the width on the current line, and start a new line when the width would exceed 100.

Steps

• Initialize line count to 1 and current line width to 0
• For each character in the string:
  • Get its width from the widths array
  • If adding this width would exceed 100, increment line count and reset current width
  • Add the character’s width to the current line
• Return the line count and final line width

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        lines = 1
        current_width = 0
        
        for char in s:
            char_width = widths[ord(char) - ord('a')]
            if current_width + char_width > 100:
                lines += 1
                current_width = char_width
            else:
                current_width += char_width
        
        return [lines, current_width]

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) - only using constant extra space
• Notes: This is the optimal solution as we must examine each character at least once.