Decremental String Concatenation

Problem

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

Solution (Java)

class Solution {
    Integer[][][] dp;
    private int solve(int i, int n, int ps, int pe, String[] words){
        // strategy is we have to just compare first and last
        // taking whole string make no sense


        if(i == n)
            return 0;

        // if present in dp
        if(dp[i][ps][pe] != null)
            return dp[i][ps][pe];


        String cur = words[i];

        int cs = cur.charAt(0)-'a';
        int ce = cur.charAt(cur.length()-1)-'a';

        // taking current word length two times for 2 next calls
        int len1 = cur.length();
        int len2 = cur.length();


        // compare middle ones
        if(pe == cs){
            len1--;     // if mid same del current words starting basically decrease length of current
        }

        if(ce == ps){
            len2--;     // if mid same del current words ending basically decrease length of current
        }


        // send two word
        int opt1 = solve(i+1, n, ps, ce, words)+len1;       // in this for next call prev+cur so ps is starting ce is ending
        int opt2 = solve(i+1, n, cs, pe, words)+len2;       // cur+prev so cs is starting and pe is ending

        return dp[i][ps][pe] = Math.min(opt1, opt2);
    }

    public int minimizeConcatenatedLength(String[] words) {

        int n = words.length;
        if(n == 1)
            return words[0].length();
        dp = new Integer[n+1][26][26];

        int ps = (int)(words[0].charAt(0)-'a');
        int pe = (int)(words[0].charAt(words[0].length()-1)-'a');
        int len = words[0].length();

        return solve(1, n, ps, pe, words)+len;
    }
}

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).