0869EasyArrayString

Rows Needed to Set the Notice

Tracked in this browser only

Trains the technique from

LeetCode 806Number of Lines To Write String

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A typesetter fills rows exactly 100 units wide. Letter 'a' takes widths[0] units, letter 'b' takes widths[1], and so on through the alphabet.

The letters of s are set in order. A letter goes on the current row when it still fits within 100 units; otherwise a new row is started and the letter goes at its beginning. No letter is ever split across two rows.

Return a list of two numbers: how many rows were used, and how many units the last row holds.

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 = "abcdefghijk"
Output: [2, 10]

Every letter takes 10 units, so ten of them exactly fill the first row and the eleventh starts a second row holding 10 units.

Example 2

Input: widths = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], s = "a"
Output: [1, 2]

A single letter of width 2 sits on the first row, which then holds 2 units.

Example 3

Input: widths = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Output: [2, 2]

Fifty letters of width 2 fill the first row exactly, so the fifty-first starts a second row.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def rows_needed(widths: list[int], s: str) -> list[int]:

Java

public int[] rowsNeeded(int[] widths, String s)

The intended approach

Time O(n) for a notice of n letters: constant work each.Space O(1).

Keep a row count and the units used on the current row, both starting from one empty row. For each letter, look up its width and check whether adding it would pass the row limit; if it would, close the row and start a fresh one holding just that letter. Because no letter is wider than the limit, a single letter always fits on an empty row and the walk never stalls.

Pythonentry point: rows_needed

def rows_needed(widths, s):
    rows = 1
    used = 0
    for ch in s:
        w = widths[ord(ch) - 97]
        if used + w > 100:
            rows += 1
            used = w
        else:
            used += w
    return [rows, used]

The obvious version

Lay the letters out into an explicit list of rows, appending to the last row when it still fits and starting a new list otherwise, then report how many rows there are and add up the widths on the final one.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_rows_needed(widths, s):
    lines = [[]]
    for ch in s:
        w = widths[ord(ch) - 97]
        total = 0
        for got in lines[-1]:
            total += got
        if total + w > 100:
            lines.append([w])
        else:
            lines[-1].append(w)
    last = 0
    for got in lines[-1]:
        last += got
    return [len(lines), last]

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in