# 2746. Decremental String Concatenation

## Description

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. 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

## Solutions

• class Solution {
private Integer[][][] f;
private String[] words;
private int n;

public int minimizeConcatenatedLength(String[] words) {
n = words.length;
this.words = words;
f = new Integer[n];
return words.length()
+ dfs(1, words.charAt(0) - 'a', words.charAt(words.length() - 1) - 'a');
}

private int dfs(int i, int a, int b) {
if (i >= n) {
return 0;
}
if (f[i][a][b] != null) {
return f[i][a][b];
}
String s = words[i];
int m = s.length();
int x = dfs(i + 1, a, s.charAt(m - 1) - 'a') - (s.charAt(0) - 'a' == b ? 1 : 0);
int y = dfs(i + 1, s.charAt(0) - 'a', b) - (s.charAt(m - 1) - 'a' == a ? 1 : 0);
return f[i][a][b] = m + Math.min(x, y);
}
}

• class Solution {
public:
int minimizeConcatenatedLength(vector<string>& words) {
int n = words.size();
int f[n];
memset(f, 0, sizeof(f));
function<int(int, int, int)> dfs = [&](int i, int a, int b) {
if (i >= n) {
return 0;
}
if (f[i][a][b]) {
return f[i][a][b];
}
auto s = words[i];
int m = s.size();
int x = dfs(i + 1, a, s[m - 1] - 'a') - (s - 'a' == b);
int y = dfs(i + 1, s - 'a', b) - (s[m - 1] - 'a' == a);
return f[i][a][b] = m + min(x, y);
};
return words.size() + dfs(1, words.front() - 'a', words.back() - 'a');
}
};

• class Solution:
def minimizeConcatenatedLength(self, words: List[str]) -> int:
@cache
def dfs(i: int, a: str, b: str) -> int:
if i >= len(words):
return 0
s = words[i]
x = dfs(i + 1, a, s[-1]) - int(s == b)
y = dfs(i + 1, s, b) - int(s[-1] == a)
return len(s) + min(x, y)

return len(words) + dfs(1, words, words[-1])


• func minimizeConcatenatedLength(words []string) int {
n := len(words)
f := make([]int, n)
var dfs func(i, a, b int) int
dfs = func(i, a, b int) int {
if i >= n {
return 0
}
if f[i][a][b] > 0 {
return f[i][a][b]
}
s := words[i]
m := len(s)
x := dfs(i+1, a, int(s[m-1]-'a'))
y := dfs(i+1, int(s-'a'), b)
if int(s-'a') == b {
x--
}
if int(s[m-1]-'a') == a {
y--
}
f[i][a][b] = m + min(x, y)
return f[i][a][b]
}
return len(words) + dfs(1, int(words-'a'), int(words[len(words)-1]-'a'))
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

• function minimizeConcatenatedLength(words: string[]): number {
const n = words.length;
const f: number[][][] = Array(n)
.fill(0)
.map(() =>
Array(26)
.fill(0)
.map(() => Array(26).fill(0)),
);
const dfs = (i: number, a: number, b: number): number => {
if (i >= n) {
return 0;
}
if (f[i][a][b] > 0) {
return f[i][a][b];
}
const s = words[i];
const m = s.length;
const x =
dfs(i + 1, a, s[m - 1].charCodeAt(0) - 97) - (s.charCodeAt(0) - 97 === b ? 1 : 0);
const y =
dfs(i + 1, s.charCodeAt(0) - 97, b) - (s[m - 1].charCodeAt(0) - 97 === a ? 1 : 0);
return (f[i][a][b] = Math.min(x + m, y + m));
};
return (
words.length +
dfs(1, words.charCodeAt(0) - 97, words[words.length - 1].charCodeAt(0) - 97)
);
}