Skip to main content
Talentd

Minimum Cost to Separate Sentence Into Rows - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming14 min readAsked at: Microsoft
Practice this problem

Problem Statement

You are given a string sentence containing words separated by spaces, and an integer k. Your task is to separate sentence into rows where the number of characters in each row is at most k. You may assume that sentence does not begin or end with a space, and the words in sentence are separated by a single space.

You can split sentence into rows by inserting line breaks between words in sentence. A word cannot be split between two rows. Each word must be used exactly once, and the word order cannot be rearranged. Adjacent words in a row should be separated by a single space, and rows should not begin or end with spaces.

The cost of a row with length n is (k - n)2, and the total cost is the sum of the costs for all rows except the last one.

  • For example if sentence = "i love leetcode" and k = 12:
    • Separating sentence into "i", "love", and "leetcode" has a cost of (12 - 1)2 + (12 - 4)2 = 185.
    • Separating sentence into "i love", and "leetcode" has a cost of (12 - 6)2 = 36.
    • Separating sentence into "i", and "love leetcode" is not possible because the length of "love leetcode" is greater than k.

Return the minimum possible total cost of separating sentence into rows.

 

Example 1:

Input: sentence = "i love leetcode", k = 12
Output: 36
Explanation:
Separating sentence into "i", "love", and "leetcode" has a cost of (12 - 1)2 + (12 - 4)2 = 185.
Separating sentence into "i love", and "leetcode" has a cost of (12 - 6)2 = 36.
Separating sentence into "i", "love leetcode" is not possible because "love leetcode" has length 13.
36 is the minimum possible total cost so return it.

Example 2:

Input: sentence = "apples and bananas taste great", k = 7
Output: 21
Explanation
Separating sentence into "apples", "and", "bananas", "taste", and "great" has a cost of (7 - 6)2 + (7 - 3)2 + (7 - 7)2 + (7 - 5)2 = 21.
21 is the minimum possible total cost so return it.

Example 3:

Input: sentence = "a", k = 5
Output: 0
Explanation:
The cost of the last row is not included in the total cost, and since there is only one row, return 0.

 

Constraints:

  • 1 <= sentence.length <= 5000
  • 1 <= k <= 5000
  • The length of each word in sentence is at most k.
  • sentence consists of only lowercase English letters and spaces.
  • sentence does not begin or end with a space.
  • Words in sentence are separated by a single space.

Approach Overview

Problem Overview: Given a sentence and a maximum row width k, split the words into multiple rows. Each row must fit within k characters (including spaces between words). The cost of a row is the square of unused spaces (k - used)^2, and the last row has zero cost. The goal is to minimize the total cost.

Approach 1: Brute Force Word Partitioning (O(n^3) time, O(n) space)

Start from each word index and try placing every possible sequence of following words on the same row until the width exceeds k. For every valid break, recursively compute the cost of the remaining words. To evaluate the row width, repeatedly sum the word lengths and spaces between them. Because each width calculation may take O(n), and we explore O(n^2) partitions, the total complexity becomes O(n^3). This approach demonstrates the structure of the problem but becomes slow as the sentence grows.

Approach 2: Prefix Sum + Memoized Search (O(n^2) time, O(n) space)

Precompute a prefix sum array of word lengths so the total characters between indices i and j can be calculated in O(1). From a starting word i, iterate j forward while the row length (characters plus spaces) stays ≤ k. The unused spaces are k - currentWidth, and the row cost is (unused)^2, except when j reaches the final word where the cost becomes zero. Use memoization on index i to store the minimum cost of formatting the suffix starting at that word. Each state explores at most n transitions, giving O(n^2) time overall with O(n) memo storage.

This pattern is a classic text‑justification style dynamic programming problem. Prefix sums remove repeated length calculations, and memoization ensures each starting index is solved once. The recursion essentially decides where to place the next line break.

Recommended for interviews: The prefix sum + memoized search solution is what interviewers expect. A brute force explanation shows you understand the partitioning structure, but adding prefix sums and memoization reduces repeated work and demonstrates strong dynamic programming reasoning with efficient range calculations using arrays. The optimized solution runs in O(n^2) time and scales comfortably for typical constraints.

Solution

We use an array nums to record the length of each word, and let the length of the array be n. Then we define a prefix sum array s of length n + 1, where s[i] represents the sum of the lengths of the first i words.

Next, we design a function dfs(i), which represents the minimum cost of splitting the sentence starting from the i-th word. The answer is dfs(0).

The execution process of the function dfs(i) is as follows:

  • If the sum of the lengths of the words from the i-th word to the last word plus the number of spaces between the words is less than or equal to k, then these words can be placed on the last line, and the cost is 0.
  • Otherwise, we enumerate the position j of the next word to start splitting, such that the sum of the lengths of the words from the i-th word to the (j-1)-th word plus the number of spaces between the words is less than or equal to k. Then dfs(j) represents the minimum cost of splitting the sentence starting from the j-th word, and (k - m)^2 represents the cost of placing the words from the i-th word to the (j-1)-th word on one line, where m represents the sum of the lengths of the words from the i-th word to the (j-1)-th word plus the number of spaces between the words. We enumerate all j and take the minimum value.

The answer is dfs(0).

To avoid repeated calculations, we can use memoized search.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the number of words.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Word PartitioningO(n^3)O(n)Understanding the basic recursive structure of trying all line breaks
Dynamic Programming with Prefix Sums + MemoizationO(n^2)O(n)General optimal solution for minimizing formatting cost

Video Solution

2052. Minimum Cost to Separate Sentence Into Rows (Leetcode Medium) • Programming Live with Larry • 188 views views

Frequently Asked Questions

Is Minimum Cost to Separate Sentence Into Rows easy or hard?
Minimum Cost to Separate Sentence Into Rows is typically rated Medium difficulty. The challenge is recognizing the dynamic programming structure and avoiding repeated width calculations. Once prefix sums and memoization are applied, the implementation becomes straightforward.
Minimum Cost to Separate Sentence Into Rows Python/Java solution
The standard implementation uses a DP function with memoization. Python often uses recursion with functools.lru_cache, while Java uses an integer array for memo storage. Both compute row width using prefix sums and iterate through valid row endings to minimize the squared unused space cost.
How to solve Minimum Cost to Separate Sentence Into Rows in O(n^2)?
Precompute prefix sums of word lengths to quickly calculate the character count between any two indices. Use recursion or DP where dp[i] represents the minimum cost starting from word i. Expand the row from i to j while the total width stays ≤ k, compute the unused space cost, and combine it with dp[j+1]. Memoization reduces repeated work, giving O(n^2) time.
What is the best approach for Minimum Cost to Separate Sentence Into Rows?
The most efficient solution uses dynamic programming with prefix sums and memoized recursion. From each word index, try extending the row while the width remains within k and compute the unused spaces. Prefix sums allow O(1) length calculations, and memoization ensures each starting index is solved once. This results in O(n^2) time and O(n) space.
Is Minimum Cost to Separate Sentence Into Rows asked at Google/Amazon/Meta?
Problems based on text formatting and word wrapping appear in interviews at companies like Google, Amazon, and Meta. They test dynamic programming, optimal partitioning, and efficient range calculations. Variants of the classic word wrap problem are common in system and algorithm interviews.
What data structure is used in Minimum Cost to Separate Sentence Into Rows?
The main structures are arrays for storing word lengths, a prefix sum array for fast range calculations, and a memoization table or DP array for caching results. These structures support efficient dynamic programming transitions between word indices.
What is the time complexity of Minimum Cost to Separate Sentence Into Rows?
The optimal solution runs in O(n^2) time where n is the number of words. For each starting word, the algorithm iterates forward to test valid row endings. Memoization prevents recomputation, so each state is evaluated once with up to n transitions.

Ready to solve this problem?

Practice Minimum Cost to Separate Sentence Into Rows with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sentence Screen Fitting