2052. Minimum Cost to Separate Sentence Into Rows

Description

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.

For example if sentence = "i love leetcode" and k = 12:
- Separating sentence into "i", "love", and "leetcode" has a cost of (12 - 1)² + (12 - 4)² = 185.
- Separating sentence into "i love", and "leetcode" has a cost of (12 - 6)² = 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)² + (12 - 4)² = 185.
Separating sentence into "i love", and "leetcode" has a cost of (12 - 6)² = 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)² + (7 - 3)² + (7 - 7)² + (7 - 5)²= 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.

Solutions

Solution 2: Prefix Sum + Dynamic Programming

Thinking

Listing every set of line breaks is exponential. The sentence length reaches $5000$, and the next line is always tried at the following word first, so the search is as deep as the number of words. The minimum cost from word $i$ depends only on later words. Prefix sums give a line width in constant time. Let $f[i]$ be that cost, zero when the remaining words fit on the last line, and otherwise fill from the right by adding $(k-m)^2+f[j]$.

Let $s[i]$ be the total length of the first $i$ words, and let $n$ be the number of words. Let $f[i]$ be the minimum cost of typesetting from word $i$. For $i$ from $n-1$ down to $0$, if the words from $i$ through the end, plus the spaces between them, fit in $k$, they form the last line and $f[i]=0$. Otherwise enumerate the next line start $j$ such that the width $m$ of words $i$ through $j-1$, including spaces, is at most $k$, and update $f[i]$ with $(k-m)^2+f[j]$. The answer is $f[0]$.

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

class Solution {
    private static final int INF = Integer.MAX_VALUE;
    private int[] memo;
    private int[] s;
    private int n;

    public int minimumCost(String sentence, int k) {
        String[] words = sentence.split(" ");
        n = words.length;
        s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + words[i].length();
        }
        memo = new int[n];
        Arrays.fill(memo, INF);
        return dfs(0, k);
    }

    private int dfs(int i, int k) {
        if (memo[i] != INF) {
            return memo[i];
        }
        if (s[n] - s[i] + n - i - 1 <= k) {
            memo[i] = 0;
            return 0;
        }
        int ans = INF;
        for (int j = i + 1; j < n; ++j) {
            int t = s[j] - s[i] + j - i - 1;
            if (t <= k) {
                ans = Math.min(ans, (k - t) * (k - t) + dfs(j, k));
            }
        }
        memo[i] = ans;
        return ans;
    }
}


// Solution 2
class Solution {
    public int minimumCost(String sentence, int k) {
        String[] words = sentence.split(" ");
        int n = words.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + words[i].length();
        }
        int[] f = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            if (s[n] - s[i] + n - i - 1 <= k) {
                continue;
            }
            int ans = Integer.MAX_VALUE;
            for (int j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
                int m = s[j] - s[i] + j - i - 1;
                ans = Math.min(ans, f[j] + (k - m) * (k - m));
            }
            f[i] = ans;
        }
        return f[0];
    }
}

class Solution {
public:
    const int inf = INT_MAX;
    int n;

    int minimumCost(string sentence, int k) {
        istringstream is(sentence);
        vector<string> words;
        string word;
        while (is >> word) words.push_back(word);
        n = words.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) s[i + 1] = s[i] + words[i].size();
        vector<int> memo(n, inf);
        return dfs(0, k, s, memo);
    }

    int dfs(int i, int k, vector<int>& s, vector<int>& memo) {
        if (memo[i] != inf) return memo[i];
        if (s[n] - s[i] + n - i - 1 <= k) {
            memo[i] = 0;
            return 0;
        }
        int ans = inf;
        for (int j = i + 1; j < n; ++j) {
            int t = s[j] - s[i] + j - i - 1;
            if (t <= k) ans = min(ans, (k - t) * (k - t) + dfs(j, k, s, memo));
        }
        memo[i] = ans;
        return ans;
    }
};


// Solution 2
class Solution {
public:
    int minimumCost(string sentence, int k) {
        istringstream iss(sentence);
        vector<int> s = {0};
        string w;
        while (iss >> w) {
            s.push_back(s.back() + (int) w.size());
        }
        int n = s.size() - 1;
        vector<int> f(n);
        for (int i = n - 1; i >= 0; --i) {
            if (s[n] - s[i] + n - i - 1 <= k) {
                continue;
            }
            int ans = INT_MAX;
            for (int j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
                int m = s[j] - s[i] + j - i - 1;
                ans = min(ans, f[j] + (k - m) * (k - m));
            }
            f[i] = ans;
        }
        return f[0];
    }
};

class Solution:
    def minimumCost(self, sentence: str, k: int) -> int:
        @cache
        def dfs(i):
            if s[-1] - s[i] + n - i - 1 <= k:
                return 0
            ans, j = inf, i + 1
            while j < n and (t := s[j] - s[i] + j - i - 1) <= k:
                ans = min(ans, (k - t) ** 2 + dfs(j))
                j += 1
            return ans

        t = [len(w) for w in sentence.split()]
        n = len(t)
        s = list(accumulate(t, initial=0))
        return dfs(0)



# Solution 2
class Solution:
    def minimumCost(self, sentence: str, k: int) -> int:
        nums = [len(w) for w in sentence.split()]
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        f = [0] * n
        for i in range(n - 1, -1, -1):
            if s[n] - s[i] + n - i - 1 <= k:
                continue
            ans = inf
            j = i + 1
            while j < n and (m := s[j] - s[i] + j - i - 1) <= k:
                ans = min(ans, f[j] + (k - m) ** 2)
                j += 1
            f[i] = ans
        return f[0]

func minimumCost(sentence string, k int) int {
	words := strings.Split(sentence, " ")
	n := len(words)
	inf := math.MaxInt32
	s := make([]int, n+1)
	for i, word := range words {
		s[i+1] = s[i] + len(word)
	}
	memo := make([]int, n)
	for i := range memo {
		memo[i] = inf
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if memo[i] != inf {
			return memo[i]
		}
		if s[n]-s[i]+n-i-1 <= k {
			memo[i] = 0
			return 0
		}
		ans := inf
		for j := i + 1; j < n; j++ {
			t := s[j] - s[i] + j - i - 1
			if t <= k {
				ans = min(ans, (k-t)*(k-t)+dfs(j))
			}
		}
		memo[i] = ans
		return ans
	}
	return dfs(0)
}


// Solution 2
func minimumCost(sentence string, k int) int {
	s := []int{0}
	for _, w := range strings.Split(sentence, " ") {
		s = append(s, s[len(s)-1]+len(w))
	}
	n := len(s) - 1
	f := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		if s[n]-s[i]+n-i-1 <= k {
			continue
		}
		ans := math.MaxInt32
		for j := i + 1; j < n && s[j]-s[i]+j-i-1 <= k; j++ {
			m := s[j] - s[i] + j - i - 1
			ans = min(ans, f[j]+(k-m)*(k-m))
		}
		f[i] = ans
	}
	return f[0]
}

function minimumCost(sentence: string, k: number): number {
    const s: number[] = [0];
    for (const w of sentence.split(' ')) {
        s.push(s.at(-1)! + w.length);
    }
    const n = s.length - 1;
    const f: number[] = Array(n).fill(-1);
    const dfs = (i: number): number => {
        if (s[n] - s[i] + n - i - 1 <= k) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        let ans = Infinity;
        for (let j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
            const m = s[j] - s[i] + j - i - 1;
            ans = Math.min(ans, dfs(j) + (k - m) ** 2);
        }
        return (f[i] = ans);
    };
    return dfs(0);
}



// Solution 2
function minimumCost(sentence: string, k: number): number {
    const s: number[] = [0];
    for (const w of sentence.split(' ')) {
        s.push(s.at(-1)! + w.length);
    }
    const n = s.length - 1;
    const f: number[] = Array(n).fill(0);
    for (let i = n - 1; i >= 0; --i) {
        if (s[n] - s[i] + n - i - 1 <= k) {
            continue;
        }
        let ans = Infinity;
        for (let j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
            const m = s[j] - s[i] + j - i - 1;
            ans = Math.min(ans, f[j] + (k - m) ** 2);
        }
        f[i] = ans;
    }
    return f[0];
}

2052 - Minimum Cost to Separate Sentence Into Rows

2052. Minimum Cost to Separate Sentence Into Rows

Description

Solutions

Solution 2: Prefix Sum + Dynamic Programming

All Problems

All Solutions

Welcome to Subscribe On Youtube

2052. Minimum Cost to Separate Sentence Into Rows

Description

Solutions

Solution 2: Prefix Sum + Dynamic Programming

All Problems

All Solutions