Minimum Cost to Separate Sentence Into Rows

Minimum Cost to Separate Sentence Into Rows - 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 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)², and the total cost is the sum of the costs for all rows except the last one.

Example: If sentence = "i love leetcode" and k = 12:
• Separating sentence into "i", "love", and "leetcode" has a cost of (12 - 1)² + (12 - 4)² = 121 + 64 = 185
• Separating sentence into "i love", and "leetcode" has a cost of (12 - 6)² = 36

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

Input & Output

Example 1 — Basic Case

$ Input: sentence = "i love leetcode", k = 12

› Output: 36

💡 Note: Split into "i love" (6 chars) and "leetcode" (8 chars). Cost = (12-6)² = 36. Last row has no cost.

Example 2 — Single Word Per Row

$ Input: sentence = "hello world", k = 8

› Output: 25

💡 Note: Split into "hello" (5 chars) and "world" (5 chars). Cost = (8-5)² = 9. Wait, "hello world" = 11 chars > 8, so must split. Cost = (8-5)² = 9.

Example 3 — All Words Fit

$ Input: sentence = "a b c", k = 10

› Output: 0

💡 Note: All words fit in one row: "a b c" (5 chars ≤ 10). Since it's the last (and only) row, cost = 0.

Constraints

1 ≤ sentence.length ≤ 500
1 ≤ k ≤ 500
sentence consists of only lowercase English letters and spaces
sentence does not start or end with a space
Words in sentence are separated by a single space

Visualization

Tap to expand

Understanding the Visualization

Input

sentence = "i love leetcode", k = 12

Split Options

Try different ways to break into rows

Calculate Cost

Cost = (k - length)² for each row except last

Key Takeaway

🎯 Key Insight: Use dynamic programming to find optimal split points that minimize total cost

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is to use dynamic programming where each position represents the minimum cost to format remaining words. The optimal approach uses bottom-up DP to avoid recursion overhead. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n³)	O(n)	Use recursion with caching to avoid recalculating same subproblems
Brute Force Recursion	O(2^n)	O(n)	Try all possible ways to split the sentence and find minimum cost
Bottom-Up Dynamic Programming	O(n³)	O(n)	Build solution from bottom up using 1D DP array

Memoization (Top-Down DP) — Algorithm Steps

Create memoization cache
For each position, check cache first
If not cached, calculate recursively and store result
Return cached minimum cost

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cache

Look up if result for current position exists

Calculate

If not cached, solve recursively

Store Result

Cache the result for future use

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int memo[1000];
int memoSet[1000];

int solve(char words[][100], int start, int n, int k) {
    if (start == n) {
        return 0;
    }
    
    if (memoSet[start]) {
        return memo[start];
    }
    
    int minCost = INT_MAX;
    int length = 0;
    
    for (int end = start; end < n; end++) {
        if (length > 0) {
            length += 1;  // space
        }
        length += strlen(words[end]);
        
        if (length > k) {
            break;
        }
        
        int cost = 0;
        if (end == n - 1) {  // last row has no cost
            cost = 0;
        } else {
            cost = (k - length) * (k - length);
        }
        
        int remainingCost = solve(words, end + 1, n, k);
        if (cost + remainingCost < minCost) {
            minCost = cost + remainingCost;
        }
    }
    
    memo[start] = minCost;
    memoSet[start] = 1;
    return minCost;
}

int solution(char* sentence, int k) {
    char words[100][100];
    int n = 0;
    
    memset(memoSet, 0, sizeof(memoSet));
    
    char* token = strtok(sentence, " ");
    while (token != NULL && n < 100) {
        strcpy(words[n], token);
        n++;
        token = strtok(NULL, " ");
    }
    
    return solve(words, 0, n, k);
}

int main() {
    char sentence[1000];
    int k;
    
    fgets(sentence, sizeof(sentence), stdin);
    sentence[strcspn(sentence, "\n")] = 0;
    
    scanf("%d", &k);
    
    int result = solution(sentence, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

n positions × n possible row lengths × n word length calculations

⚠ Quadratic Growth

Space Complexity

O(n)

Memoization array of size n plus recursion stack

⚡ Linearithmic Space

21.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler