Minimum Cost to Separate Sentence Into Rows
01 · Problem
You are given a string sentence of words separated by single spaces (no leading or trailing spaces) and an integer k. Split the sentence into one or more rows by placing line breaks between words; words keep their order and may not be broken across rows. Inside a row, words are separated by a single space, so a row's length is the sum of its word lengths plus the number of spaces between them. Every row must have length at most k.
The cost of a row with length len is (k - len)^2, and the total cost is the sum of the costs of all rows except the last one. Return the minimum possible total cost. Every word is guaranteed to fit on a row by itself, and a sentence that fits on a single row costs 0.
02 · Examples
sentence = "the quick brown fox", k = 10
1
Rows "the quick" (length 9, cost (10 - 9)^2 = 1) and "brown fox" (the last row, free). Total 1.
sentence = "a bb ccc dd e", k = 6
4
Rows "a bb" (length 4, cost 4), "ccc dd" (length 6, cost 0), and "e" (last row, free). Total 4; any other split costs more.
sentence = "hello", k = 5
0
The only row is the last row, so it costs nothing.
03 · Constraints
- 011 <= sentence.length <= 5000
- 021 <= k <= 5000
- 03Every word's length is at most k
- 04sentence consists of lowercase English letters and single spaces
- 05sentence has no leading or trailing spaces
04 · Optimal complexity
- Time
- O(w * min(w, k))
- Space
- O(w)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.