LeetCode 2052: Minimum Cost to Separate Sentence Into Rows Solution

Master LeetCode problem 2052 (Minimum Cost to Separate Sentence Into Rows), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2052. Minimum Cost to Separate Sentence Into Rows

Medium

Array Dynamic Programming

Problem Explanation

Explanation:

Given a sentence and a maximum column width, we need to separate the sentence into rows such that each row does not exceed the column width. The cost of a row is calculated as the square of the extra spaces at the end of the row. The total cost is the sum of costs for all rows.

To solve this problem, we can use dynamic programming. We iterate through each word in the sentence and try to fit as many words as possible in a row without exceeding the column width. At each step, we calculate the cost of the current row and update the minimum cost for reaching that word. :

Solution Code

class Solution {
    public int minimumCostToSeparateSentenceIntoRows(String sentence, int columnWidth) {
        String[] words = sentence.split(" ");
        int n = words.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            int remainingWidth = columnWidth - words[i - 1].length();
            dp[i] = dp[i - 1] + remainingWidth * remainingWidth;

            for (int j = i - 2; j >= 0; j--) {
                remainingWidth -= (words[j].length() + 1); // +1 for space
                if (remainingWidth < 0) break;
                dp[i] = Math.min(dp[i], dp[j] + remainingWidth * remainingWidth);
            }
        }

        return dp[n];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2052 (Minimum Cost to Separate Sentence Into Rows)?

This page provides optimized solutions for LeetCode problem 2052 (Minimum Cost to Separate Sentence Into Rows) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2052 (Minimum Cost to Separate Sentence Into Rows)?

The time complexity for LeetCode 2052 (Minimum Cost to Separate Sentence Into Rows) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2052 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2052 in Java, C++, or Python.

Back to LeetCode Solutions