# Decremental String Concatenation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/decremental-string-concatenation)
Canonical: https://scaleengineer.com/dsa/problems/decremental-string-concatenation
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, String
---
## 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

# Approaches
## Top-Down Dynamic Programming (Memoization)
This approach uses recursion with memoization to solve the problem. It explores all possible ways of joining the strings and stores the results of subproblems to avoid redundant calculations. The state of our recursive function is defined by the index of the current word being processed, and the first and last characters of the string formed so far.
**Time:** O(N * C^3), where N is the number of words and C is the alphabet size (26). For each state `(i, f, l)`, we iterate through C possible previous characters. · **Space:** O(N * C^2), where N is the number of words and C is the alphabet size (26). This is for the memoization table.
**Pros:** Conceptually straightforward, as it directly translates the recursive structure of the problem.; Avoids recomputing solutions to the same subproblem through memoization.
**Cons:** Higher time complexity compared to the bottom-up approach due to an extra loop over the alphabet in the recursive step.; Can lead to stack overflow for very deep recursion, although the constraint `n <= 1000` is generally manageable.; Uses more space than the optimized bottom-up approach.
### Explanation
We define a recursive function, say `solve(i, firstChar, lastChar)`, which calculates the minimum length of a string formed by joining `words[0]` through `words[i]` that starts with `firstChar` and ends with `lastChar`. The state is `(i, firstChar, lastChar)`, representing the subproblem for `words[0...i]`. We use a 3D array `memo[i][firstChar - 'a'][lastChar - 'a']` to store the results.

**Base Case**: For `i = 0`, the string is just `words[0]`. The length is `words[0].length()`, and the first and last characters are fixed. For any other combination of first/last characters, the length is considered infinite.

**Recursive Step**: To compute `solve(i, f, l)`, we consider how a string with first char `f` and last char `l` could have been formed at step `i`. There are two possibilities for the `i`-th join operation:
1. `str_i = join(str_{i-1}, words[i])`: The new first character `f` must be the same as the first character of `str_{i-1}`, and the new last character `l` must be the last character of `words[i]`. We iterate through all possible last characters of `str_{i-1}` to find the minimum length.
2. `str_i = join(words[i], str_{i-1})`: The new first character `f` must be the first character of `words[i]`, and the new last character `l` must be the same as the last character of `str_{i-1}`. We iterate through all possible first characters of `str_{i-1}`.

The function returns the minimum length found. The final answer is the minimum value among `solve(n-1, f, l)` for all possible `f` and `l`.

```java
class Solution {
    private Integer[][][] memo;
    private String[] words;
    private int n;
    private final int INF = 1_000_000_000;

    public int minimizeConcatenatedLength(String[] words) {
        this.words = words;
        this.n = words.length;
        if (n == 1) {
            return words[0].length();
        }
        this.memo = new Integer[n][26][26];

        int minLength = INF;
        for (char first = 'a'; first <= 'z'; first++) {
            for (char last = 'a'; last <= 'z'; last++) {
                minLength = Math.min(minLength, solve(n - 1, first, last));
            }
        }
        return minLength;
    }

    private int solve(int i, char first, char last) {
        if (i == 0) {
            String w = words[0];
            if (w.charAt(0) == first && w.charAt(w.length() - 1) == last) {
                return w.length();
            }
            return INF;
        }

        if (memo[i][first - 'a'][last - 'a'] != null) {
            return memo[i][first - 'a'][last - 'a'];
        }

        int minLen = INF;
        String w = words[i];
        char wFirst = w.charAt(0);
        char wLast = w.charAt(w.length() - 1);
        int wLen = w.length();

        // Case 1: str_i = join(str_{i-1}, words[i])
        if (last == wLast) {
            for (char prevLast = 'a'; prevLast <= 'z'; prevLast++) {
                int prevLen = solve(i - 1, first, prevLast);
                if (prevLen != INF) {
                    int currentLen = prevLen + wLen - (prevLast == wFirst ? 1 : 0);
                    minLen = Math.min(minLen, currentLen);
                }
            }
        }

        // Case 2: str_i = join(words[i], str_{i-1})
        if (first == wFirst) {
            for (char prevFirst = 'a'; prevFirst <= 'z'; prevFirst++) {
                int prevLen = solve(i - 1, prevFirst, last);
                if (prevLen != INF) {
                    int currentLen = prevLen + wLen - (wLast == prevFirst ? 1 : 0);
                    minLen = Math.min(minLen, currentLen);
                }
            }
        }

        return memo[i][first - 'a'][last - 'a'] = minLen;
    }
}
```
### Algorithm
- Create a 3D memoization table `memo[n][26][26]` initialized with a value indicating "not computed".
- Define a recursive function `solve(i, first, last)` that computes the minimum length of a string formed from `words[0...i]` starting with `first` and ending with `last`.
- **Base Case**: If `i == 0`, the function returns `words[0].length()` if `first` and `last` match the boundaries of `words[0]`, otherwise, it returns a value representing infinity.
- **Recursive Step**: For `solve(i, first, last)`, check the memoization table. If the value is not computed, calculate it by considering two cases:
  1. The string was formed by `join(str_{i-1}, words[i])`. This is possible if `last` equals the last character of `words[i]`. We recursively call `solve(i-1, first, prev_last)` for all possible `prev_last` characters ('a' through 'z') and find the minimum length.
  2. The string was formed by `join(words[i], str_{i-1})`. This is possible if `first` equals the first character of `words[i]`. We recursively call `solve(i-1, prev_first, last)` for all possible `prev_first` characters and find the minimum length.
- Store the computed minimum length in the memoization table and return it.
- The final answer is the minimum value returned by `solve(n-1, f, l)` over all possible characters `f` and `l`.

## Bottom-Up Dynamic Programming
This approach builds the solution iteratively from the base case up to the final solution. We use a 3D DP table `dp[i][first_char][last_char]` to store the minimum length of the string formed by `words[0...i]` with specific first and last characters. This avoids recursion and improves efficiency over the top-down approach.
**Time:** O(N * C^2), where N is the number of words and C is the alphabet size (26). We have three nested loops: `i` up to N, and two loops for characters up to C. · **Space:** O(N * C^2), where N is the number of words and C is the alphabet size (26), for the 3D DP table.
**Pros:** More efficient time complexity than the top-down approach.; Iterative nature avoids recursion overhead and potential stack overflow issues.
**Cons:** Uses O(N * C^2) space, which is not optimal and can be improved.
### Explanation
We define a 3D DP table `dp[n][26][26]`. `dp[i][j][k]` will store the minimum length of the concatenated string using `words[0]` to `words[i]`, where the resulting string starts with character `'a' + j` and ends with character `'a' + k`.

**Initialization**: Initialize the `dp` table with a large value (infinity) to represent unreachable states.

**Base Case**: For `i = 0`, the string is `words[0]`. We set `dp[0][words[0].charAt(0) - 'a'][words[0].charAt(words[0].length()-1) - 'a'] = words[0].length()`.

**Transition**: We iterate from `i = 1` to `n-1`. For each `i`, we compute `dp[i]` based on the values in `dp[i-1]`. For every valid state `(prev_first, prev_last)` at step `i-1` (i.e., `dp[i-1][prev_first][prev_last]` is not infinity), we consider the two choices for joining `words[i]`:
1. `join(str_{i-1}, words[i])`: The new string starts with `prev_first` and ends with the last character of `words[i]`. We calculate the new length and update `dp[i][prev_first][words[i].last]`. 
2. `join(words[i], str_{i-1})`: The new string starts with the first character of `words[i]` and ends with `prev_last`. We calculate the new length and update `dp[i][words[i].first][prev_last]`.

**Final Answer**: After filling the table up to `i = n-1`, the minimum value in the `dp[n-1]` slice is the answer.

```java
import java.util.Arrays;

class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        int n = words.length;
        if (n == 1) {
            return words[0].length();
        }
        int INF = 1_000_000_000;
        int[][][] dp = new int[n][26][26];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 26; j++) {
                Arrays.fill(dp[i][j], INF);
            }
        }

        String w0 = words[0];
        int first0 = w0.charAt(0) - 'a';
        int last0 = w0.charAt(w0.length() - 1) - 'a';
        dp[0][first0][last0] = w0.length();

        for (int i = 1; i < n; i++) {
            String w = words[i];
            int wFirst = w.charAt(0) - 'a';
            int wLast = w.charAt(w.length() - 1) - 'a';
            int wLen = w.length();

            for (int prevFirst = 0; prevFirst < 26; prevFirst++) {
                for (int prevLast = 0; prevLast < 26; prevLast++) {
                    if (dp[i - 1][prevFirst][prevLast] == INF) {
                        continue;
                    }

                    int prevLen = dp[i - 1][prevFirst][prevLast];

                    // Option 1: join(str_{i-1}, words[i])
                    int newLen1 = prevLen + wLen - (prevLast == wFirst ? 1 : 0);
                    dp[i][prevFirst][wLast] = Math.min(dp[i][prevFirst][wLast], newLen1);

                    // Option 2: join(words[i], str_{i-1})
                    int newLen2 = prevLen + wLen - (wLast == prevFirst ? 1 : 0);
                    dp[i][wFirst][prevLast] = Math.min(dp[i][wFirst][prevLast], newLen2);
                }
            }
        }

        int minLength = INF;
        for (int j = 0; j < 26; j++) {
            for (int k = 0; k < 26; k++) {
                minLength = Math.min(minLength, dp[n - 1][j][k]);
            }
        }

        return minLength;
    }
}
```
### Algorithm
- Create a 3D DP table `dp[n][26][26]` and initialize all entries to a large value (infinity).
- Set the base case for `i = 0`: `dp[0][words[0].first - 'a'][words[0].last - 'a'] = words[0].length()`.
- Iterate `i` from 1 to `n-1`:
  - For each `i`, iterate through all possible previous first characters `prev_first` ('a' to 'z') and previous last characters `prev_last` ('a' to 'z').
  - If `dp[i-1][prev_first-'a'][prev_last-'a']` is not infinity, it means we have a valid string from the previous step.
  - Calculate the new lengths for the two join options:
    1. `join(str_{i-1}, words[i])`: Update `dp[i][prev_first-'a'][words[i].last-'a']` with the new minimum length.
    2. `join(words[i], str_{i-1])`: Update `dp[i][words[i].first-'a'][prev_last-'a']` with the new minimum length.
- After the loops complete, find the minimum value in the `dp[n-1]` slice. This is the final answer.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient approach. It's an optimization of the bottom-up DP. We observe that to compute the DP values for the current word `words[i]`, we only need the DP values from the previous word `words[i-1]`. This allows us to reduce the space complexity by using only two 2D arrays to store the DP states for the previous and current steps, making the space complexity independent of the number of words.
**Time:** O(N * C^2), where N is the number of words and C is the alphabet size (26). The complexity remains the same as the unoptimized bottom-up DP. · **Space:** O(C^2), where C is the alphabet size (26). We use two 2D arrays of size 26x26, which is constant space with respect to N.
**Pros:** Optimal time complexity for this problem.; Optimal space complexity, as it only depends on the size of the alphabet, not the number of words.
**Cons:** Slightly more complex to implement than the non-space-optimized version due to managing two tables (`dp` and `newDp`).
### Explanation
Instead of a 3D DP table `dp[n][26][26]`, we use two 2D arrays, `dp` and `newDp`, both of size `[26][26]`. `dp` stores the minimum lengths for the string formed up to `words[i-1]`, and `newDp` will be used to compute the minimum lengths for the string formed up to `words[i]`.

**Initialization**: Initialize a `dp[26][26]` array with infinity. For the base case `i=0`, set `dp[words[0].first - 'a'][words[0].last - 'a'] = words[0].length()`.

**Transition**: Iterate from `i = 1` to `n-1`. In each iteration:
1. Create a `newDp[26][26]` array and initialize it with infinity.
2. Iterate through all possible `(prev_first, prev_last)` states in the `dp` array.
3. If a state in `dp` is reachable (not infinity), calculate the two new possible states and lengths by joining with `words[i]`, and update `newDp` accordingly.
4. After iterating through all previous states, replace `dp` with `newDp` for the next iteration.

**Final Answer**: After the loop finishes, the minimum value in the final `dp` array is the result.

```java
import java.util.Arrays;

class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        int n = words.length;
        if (n == 1) {
            return words[0].length();
        }
        int INF = 1_000_000_000;
        int[][] dp = new int[26][26];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }

        String w0 = words[0];
        int first0 = w0.charAt(0) - 'a';
        int last0 = w0.charAt(w0.length() - 1) - 'a';
        dp[first0][last0] = w0.length();

        for (int i = 1; i < n; i++) {
            int[][] newDp = new int[26][26];
            for (int[] row : newDp) {
                Arrays.fill(row, INF);
            }

            String w = words[i];
            int wFirst = w.charAt(0) - 'a';
            int wLast = w.charAt(w.length() - 1) - 'a';
            int wLen = w.length();

            for (int prevFirst = 0; prevFirst < 26; prevFirst++) {
                for (int prevLast = 0; prevLast < 26; prevLast++) {
                    if (dp[prevFirst][prevLast] == INF) {
                        continue;
                    }

                    int prevLen = dp[prevFirst][prevLast];

                    // Option 1: join(str_{i-1}, words[i])
                    int newLen1 = prevLen + wLen - (prevLast == wFirst ? 1 : 0);
                    newDp[prevFirst][wLast] = Math.min(newDp[prevFirst][wLast], newLen1);

                    // Option 2: join(words[i], str_{i-1})
                    int newLen2 = prevLen + wLen - (wLast == prevFirst ? 1 : 0);
                    newDp[wFirst][prevLast] = Math.min(newDp[wFirst][prevLast], newLen2);
                }
            }
            dp = newDp;
        }

        int minLength = INF;
        for (int j = 0; j < 26; j++) {
            for (int k = 0; k < 26; k++) {
                minLength = Math.min(minLength, dp[j][k]);
            }
        }

        return minLength;
    }
}
```
### Algorithm
- Create a 2D DP table `dp[26][26]` and initialize with infinity.
- Set the base case for `words[0]`: `dp[words[0].first - 'a'][words[0].last - 'a'] = words[0].length()`.
- Loop `i` from 1 to `n-1`:
  - Create a temporary 2D table `newDp[26][26]` initialized with infinity.
  - Let `w = words[i]`.
  - Loop `prev_first` from 0 to 25.
  - Loop `prev_last` from 0 to 25.
    - If `dp[prev_first][prev_last]` is not infinity:
      - Calculate length for `join(str_{i-1}, w)` and update `newDp`.
      - Calculate length for `join(w, str_{i-1})` and update `newDp`.
  - After iterating through all previous states, assign `newDp` to `dp` to be used in the next iteration.
- Find the minimum value in the final `dp` table.

# Solutions
### Java

```java
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][26][26];
    return words[0].length() +
           dfs(1, words[0].charAt(0) - 'a',
               words[0].charAt(words[0].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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizeConcatenatedLength(vector<string> &words) {
    int n = words.size();
    int f[n][26][26];
    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[0] - 'a' == b);
      int y = dfs(i + 1, s[0] - 'a', b) - (s[m - 1] - 'a' == a);
      return f[i][a][b] = m + min(x, y);
    };
    return words[0].size() +
           dfs(1, words[0].front() - 'a', words[0].back() - 'a');
  }
};

```

### Python

```python
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[0] == b) y = dfs(i + 1, s[0], b) - int(s[- 1] == a) return len(s) + min(x, y) return len(words[0]) + dfs(1, words[0][0], words[0][- 1])

```