Ctrl K

A Phrase on a Ticker Board

Medium
A ticker board has lines lines, each width characters wide. The same phrase, the word list words, is shown on it over and over: in order, and after the last word the phrase starts again from the first. The rules are: - a word cannot be split across lines; if it does not fit in what is left of a line, it moves to the next one; - neighbouring words on one line are separated by exactly one space; - the word order never changes. How many times is the phrase shown in full?
Example 1
words=["sale", "today"], lines=3, width=10 → 3

The board lines are "sale today", "sale today", "sale today": the whole phrase runs 3 times.

Example 2
words=["go", "north", "x"], lines=4, width=7 → 2

Lines: "go", "north x", "go", "north x" (north does not fit after go: 2 + 1 + 5 = 8 > 7). The phrase runs 2 times.

Example 3
words=["welcome"], lines=5, width=6 → 0

The word is longer than a line, so it never fits.

Constraints
  • 1 ≤ len(words) ≤ 100
  • 1 ≤ len(words[i]) ≤ 10, and words consist of lowercase English letters
  • 1 ≤ lines, width ≤ 2·10⁴
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsSplit Into Dictionary Words MediumBit Strings on a Budget MediumWords Hidden in a Text MediumWord Growth Chain MediumBead String Without Twins Medium
loading Python…
Input
words=["sale", "today"], lines=3, width=10
Expected
3

Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.