2746. Decremental String Concatenation

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.

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        vector<vector<long long>> dp(26,vector<long long>(26,INT_MAX));
        dp[words[0].front()-'a'][words[0].back()-'a'] = words[0].length();
        for(int i = 1; i < words.size(); i++) {
            int a = words[i].front() - 'a', b = words[i].back() - 'a', len = words[i].length();
            vector<vector<long long>> dpp(26,vector<long long>(26,INT_MAX));
            for(int x = 0; x < 26; x++) for(int y = 0; y < 26; y++) {
                dpp[a][y] = min(dpp[a][y], len + dp[x][y] - (b == x));
                dpp[x][b] = min(dpp[x][b], len + dp[x][y] - (a == y));
            }
            swap(dp,dpp);
        }
        long long res = LLONG_MAX;
        for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) res = min(res, dp[i][j]);
        return res;
    }
};