We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Separate Sentence Into Rows

Number: 2082

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a sentence (a string of words separated by single spaces) and a maximum row length k, split the sentence into rows such that no row exceeds k characters. You cannot break a word between rows and must preserve word order. Every row (except the last) incurs a cost of (k - row_length)². The task is to determine the minimum possible total cost for such a split.

Key Insights

  • The problem is a variant of the "Word Wrap" problem where the cost for the last line is zero.
  • Use dynamic programming (DP) where dp[i] represents the minimum cost to split the sentence starting from the i-th word.
  • For each starting word index i, iterate over possible ending words j to form a valid row considering the extra spaces between words.
  • If a valid row is formed (row length ≤ k), compute:
    • If j is not the last word, add the cost (k - row_length)² plus dp[j+1].
    • If j is the last word, the cost is 0 (last line penalty is ignored).
  • The answer is dp[0], the minimum cost to arrange all words.

Space and Time Complexity

Time Complexity: O(n²), where n is the number of words. In the worst case, each word is considered with every possible ending word. Space Complexity: O(n) for storing the dp array.

Solution

We solve the problem using dynamic programming. First, split the sentence into words. Define dp[i] as the minimum cost to format the sentence from the i-th word to the end.

For each index i (starting from the last word moving backwards), try to add words one-by-one to form the current row, keeping track of the current row length (which includes words and the spaces between them). If the current row length exceeds k, break out of the inner loop. Otherwise, if j is not the last word, calculate the cost as (k - current_length)² and add dp[j + 1]. If j is the last word, there is no cost for this row (cost = 0). The minimum of these options gives dp[i].

We use iterative DP (bottom-up approach) to ensure that all subproblems are calculated before being used in the recurrence.

Code Solutions

# Python solution
def minCostToSeparateSentence(sentence, k):
    # Split the sentence into words
    words = sentence.split()
    n = len(words)
    
    # dp[i] will represent the minimum cost from word i to the end
    dp = [float('inf')] * (n + 1)
    dp[n] = 0  # no cost after the last word

    # Process words backwards
    for i in range(n - 1, -1, -1):
        current_length = 0  # current row length including words and spaces
        # Try to add words from i to j
        for j in range(i, n):
            # If this is not the first word in the row, add a space
            if j > i:
                current_length += 1  # space between words
                
            word_length = len(words[j])
            current_length += word_length
            
            # If current row exceeds k, break out as further words won't fit
            if current_length > k:
                break
            
            # If it's the last word, no cost is added (last line cost is free)
            if j == n - 1:
                cost = 0
            else:
                cost = (k - current_length) ** 2
            
            # Update dp[i] with minimum cost
            dp[i] = min(dp[i], cost + dp[j + 1])
    
    return dp[0]

# Example usage:
print(minCostToSeparateSentence("i love leetcode", 12))  # Output: 36
← Back to All Questions