2746

2746. Decremental String Concatenation (Medium)

You are given a 0-indexed array words containing n strings.

Let's define a join operation join(x, y) between two strings x and y as concatenating them into xy. However, if the last character of x is equal to the first character of y, one of them is deleted.

For example join("ab", "ba") = "aba" and join("ab", "cde") = "abcde".

You are to perform n - 1 join operations. Let str0 = words[0]. Starting from i = 1 up to i = n - 1, for the ith operation, you can do one of the following:

• Make stri = join(stri - 1, words[i])
• Make stri = join(words[i], stri - 1)

Your task is to minimize the length of strn - 1.

Return an integer denoting the minimum possible length of strn - 1.

 

Example 1:

Input: words = ["aa","ab","bc"]
Output: 4
Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: 
str0 = "aa"
str1 = join(str0, "ab") = "aab"
str2 = join(str1, "bc") = "aabc" 
It can be shown that the minimum possible length of str2 is 4.

Example 2:

Input: words = ["ab","b"]
Output: 2
Explanation: In this example, str0 = "ab", there are two ways to get str1: 
join(str0, "b") = "ab" or join("b", str0) = "bab". 
The first string, "ab", has the minimum length. Hence, the answer is 2.

Example 3:

Input: words = ["aaa","c","aba"]
Output: 6
Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: 
str0 = "aaa"
str1 = join(str0, "c") = "aaac"
str2 = join("aba", str1) = "abaaac"
It can be shown that the minimum possible length of str2 is 6.

 

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 50
• Each character in words[i] is an English lowercase letter

Related Topics:
Array, String, Dynamic Programming

Similar Questions:

• Largest Merge Of Two Strings (Medium)

Hints:

• Use dynamic programming with memoization.
• Notice that the first and last characters of a string are sufficient to determine the length of its concatenation with any other string.
• Define dp[i][first][last] as the shortest concatenation length of the first i words starting with a character first and ending with a character last. Convert characters to their ASCII codes if your programming language cannot implicitly convert them to array indices.

Solution 1. DP

Let dp[i][first][last] be the shortest length of concatenated words using A[0..i]. The answer is dp[N-1][i][j] ('a' <= i,j <= 'z').

dp[0][s[0]][s.back()] = s.size() where s = A[0]

// Denote the first and last letters in `A[i]` as `first` and `last`
// We iterate all possible values of dp[i-1][a][b]
// If append A[i]
dp[i][a][last] = min( dp[i-1][a][b] + A[i].size() - (first == b))
// If prepend A[i]
dp[i][first][b] = min( dp[i-1][a][b] + A[i].size() - (last == a))

// OJ: https://leetcode.com/problems/decremental-string-concatenation
// Author: github.com/lzl124631x
// Time: O(N * C^2) where C is the size of character set
// Space: O(C^2)
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& A) {
        unordered_map<int, int> m{{(A[0][0] - 'a') * 100 + (A[0].back() - 'a'), A[0].size()}};
        for (int i = 1; i < A.size(); ++i) {
            unordered_map<int, int> next;
            int first = A[i][0] - 'a', last = A[i].back() - 'a', newLen = A[i].size();
            for (auto &[prev, len] : m) {
                int a = prev / 100, b = prev - a * 100;
                int code1 = a * 100 + last, len1 = len + newLen - (b == first);
                if (next.count(code1) == 0 || next[code1] > len1) next[code1] = len1;
                int code2 = first * 100 + b, len2 = len + newLen - (last == a);
                if (next.count(code2) == 0 || next[code2] > len2) next[code2] = len2;
            }
            swap(next, m);
        }
        int ans = INT_MAX;
        for (auto &[_, len] : m) ans = min(ans, len);
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/decremental-string-concatenation
// Author: github.com/lzl124631x
// Time: O(N * C^2)
// Space: O(C^2)
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& A) {
        if (A.size() == 1) return A[0].size();
        int dp[26][26] = {}, ans = INT_MAX;
        dp[A[0][0] - 'a'][A[0].back() - 'a'] = A[0].size();
        for (int i = 1; i < A.size(); ++i) {
            int next[26][26] = {}, first = A[i][0] - 'a', last = A[i].back() - 'a', newLen = A[i].size();
            for (int a = 0; a < 26; ++a) {
                for (int b = 0; b < 26; ++b) {
                    if (dp[a][b] == 0) continue;
                    int len1 = dp[a][b] + newLen - (b == first);
                    if (next[a][last] == 0 || next[a][last] > len1) next[a][last] = len1;
                    int len2 = dp[a][b] + newLen - (last == a);
                    if (next[first][b] == 0 || next[first][b] > len2) next[first][b] = len2;
                    if (i == A.size() - 1) ans = min({ans, next[a][last], next[first][b]});
                }
            }
            swap(dp, next);
        }
        return ans;
    }
};