Problem

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 mostk. 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 theminimum possible total cost of separating __sentence into rows.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5

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:

1
2
3
4

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.

Solution

Method 1 – Dynamic Programming (Word Wrap)

Intuition

This is a classic word wrap problem. We use dynamic programming to find the minimum cost to split the sentence into rows, where each row’s cost is based on unused space except the last row. For each word, we try all possible previous break points and keep track of the minimum cost.

Approach

  1. Split the sentence into words.
  2. Use DP: dp[i] is the minimum cost to arrange the first i words.
  3. For each word i, try all possible previous break points j:
    • Calculate the length of the row from j to i-1 (including spaces).
    • If the row fits (<= k), update dp[i] as the minimum of its current value and dp[j] + cost (where cost is (k - row_len)^2 if not last row, else 0).
  4. Return dp[n] for the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int minimumCost(string sentence, int k) {
        vector<string> words;
        stringstream ss(sentence);
        string w;
        while (ss >> w) words.push_back(w);
        int n = words.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int len = 0;
            for (int j = i; j >= 1; --j) {
                len += words[j-1].size();
                if (i-j > 0) len++;
                if (len > k) break;
                int cost = (i == n) ? 0 : (k - len) * (k - len);
                dp[i] = min(dp[i], dp[j-1] + cost);
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func minimumCost(sentence string, k int) int {
    words := strings.Fields(sentence)
    n := len(words)
    dp := make([]int, n+1)
    for i := range dp { dp[i] = 1<<31 - 1 }
    dp[0] = 0
    for i := 1; i <= n; i++ {
        l := 0
        for j := i; j >= 1; j-- {
            l += len(words[j-1])
            if i-j > 0 { l++ }
            if l > k { break }
            cost := 0
            if i != n { cost = (k-l)*(k-l) }
            if dp[j-1]+cost < dp[i] { dp[i] = dp[j-1]+cost }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int minimumCost(String sentence, int k) {
        String[] words = sentence.split(" ");
        int n = words.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int len = 0;
            for (int j = i; j >= 1; --j) {
                len += words[j-1].length();
                if (i-j > 0) len++;
                if (len > k) break;
                int cost = (i == n) ? 0 : (k - len) * (k - len);
                dp[i] = Math.min(dp[i], dp[j-1] + cost);
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minimumCost(sentence: String, k: Int): Int {
        val words = sentence.split(" ")
        val n = words.size
        val dp = IntArray(n+1) { Int.MAX_VALUE }
        dp[0] = 0
        for (i in 1..n) {
            var len = 0
            for (j in i downTo 1) {
                len += words[j-1].length
                if (i-j > 0) len++
                if (len > k) break
                val cost = if (i == n) 0 else (k-len)*(k-len)
                dp[i] = minOf(dp[i], dp[j-1] + cost)
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def minimumCost(self, sentence: str, k: int) -> int:
        words = sentence.split()
        n = len(words)
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            l = 0
            for j in range(i, 0, -1):
                l += len(words[j-1])
                if i-j > 0:
                    l += 1
                if l > k:
                    break
                cost = 0 if i == n else (k-l)**2
                dp[i] = min(dp[i], dp[j-1] + cost)
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn minimum_cost(sentence: String, k: i32) -> i32 {
        let words: Vec<&str> = sentence.split_whitespace().collect();
        let n = words.len();
        let mut dp = vec![i32::MAX; n+1];
        dp[0] = 0;
        for i in 1..=n {
            let mut len = 0;
            for j in (1..=i).rev() {
                len += words[j-1].len();
                if i-j > 0 { len += 1; }
                if len > k as usize { break; }
                let cost = if i == n { 0 } else { (k-len as i32)*(k-len as i32) };
                dp[i] = dp[i].min(dp[j-1] + cost);
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minimumCost(sentence: string, k: number): number {
        const words = sentence.split(' ');
        const n = words.length;
        const dp = Array(n+1).fill(Infinity);
        dp[0] = 0;
        for (let i = 1; i <= n; ++i) {
            let len = 0;
            for (let j = i; j >= 1; --j) {
                len += words[j-1].length;
                if (i-j > 0) len++;
                if (len > k) break;
                const cost = i === n ? 0 : (k-len)*(k-len);
                dp[i] = Math.min(dp[i], dp[j-1] + cost);
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) where n is the number of words, due to nested loops.
  • 🧺 Space complexity: O(n) for the DP array.