Number of Lines To Write String — Easy Problem & Solution

Problem statement

You are writing s across lines that are at most 100 units wide. widths[0] is the width of 'a', widths[1] of 'b', and so on.

Write the characters in order, moving to a new line whenever the next character would push the current line past 100 units. Return [numberOfLines, widthOfLastLine].

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: Ten characters fill a line exactly; the third line holds the last six.

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: The narrow a lets eleven characters fit on the first line.

Example 3

Input: widths = [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5], s = "ab"
Output: [1,10]

Constraints

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

How to solve Number of Lines To Write String

Straight simulation. The only decision per character is whether it still fits, and that decision must be made before the character is placed.

Approach

1. Start on line 1 with 0 units used.
2. For each character, look up its width. If used + width > 100, start a new line with 0 used.
3. Add the width to used.
4. Return [lines, used].

Why it works

Greedy placement is forced — the statement gives no choice about where characters go, so the simulation is the definition.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Adding the width first and then checking for overflow miscounts the line the character lands on.
• Using >= 100 breaks a line that is exactly full, which is still legal.
• Starting the line counter at 0 undercounts by one for any non-empty string.

Reference solution

Python

from typing import List

def numberOfLines(widths: List[int], s: str) -> List[int]:
    lines, used = 1, 0
    for c in s:
        w = widths[ord(c) - 97]
        if used + w > 100:
            lines += 1
            used = 0
        used += w
    return [lines, used]

JavaScript

var numberOfLines = function(widths, s) {
    var lines = 1, used = 0;
    for (var i = 0; i < s.length; i++) {
        var w = widths[s.charCodeAt(i) - 97];
        if (used + w > 100) { lines++; used = 0; }
        used += w;
    }
    return [lines, used];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy