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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5

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

1
2
3
4
5
6
7

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

Method 1 – Dynamic Programming (State: Last Used Word)

Intuition

At each step, we can join the next word to the left or right of the current string. The optimal solution can be found by dynamic programming, where the state keeps track of which word was used last and from which side. We minimize the length by considering both options at each step.

Approach

  1. Let n be the number of words.
  2. Define dp[i][0] as the minimum length after processing the first i words, ending with the i-1th word on the left; dp[i][1] for ending with the i-1th word on the right.
  3. Initialize dp[0][0] = dp[0][1] = len(words[0]).
  4. For each i from 1 to n-1:
    • For both previous states (left/right), try joining the new word to the left or right, and update the minimum length accordingly, considering the join rule (delete one char if last of left == first of right).
  5. The answer is the minimum of the two states after all words are processed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> dp(n, vector<int>(2, INT_MAX));
        dp[0][0] = dp[0][1] = words[0].size();
        for (int i = 1; i < n; ++i) {
            for (int prev = 0; prev < 2; ++prev) {
                int l = (prev == 0) ? words[i-1][0] : words[i-1].back();
                int r = (prev == 0) ? words[i-1].back() : words[i-1][0];
                // join to right
                int cost = dp[i-1][prev] + words[i].size();
                if (r == words[i][0]) cost--;
                dp[i][0] = min(dp[i][0], cost);
                // join to left
                cost = dp[i-1][prev] + words[i].size();
                if (words[i].back() == l) cost--;
                dp[i][1] = min(dp[i][1], cost);
            }
        }
        return min(dp[n-1][0], dp[n-1][1]);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func minimizeConcatenatedLength(words []string) int {
    n := len(words)
    dp := make([][2]int, n)
    for i := range dp {
        dp[i][0], dp[i][1] = 1<<30, 1<<30
    }
    dp[0][0], dp[0][1] = len(words[0]), len(words[0])
    for i := 1; i < n; i++ {
        for prev := 0; prev < 2; prev++ {
            l := words[i-1][0]
            r := words[i-1][len(words[i-1])-1]
            if prev == 1 {
                l, r = r, l
            }
            cost := dp[i-1][prev] + len(words[i])
            if r == words[i][0] {
                cost--
            }
            if cost < dp[i][0] {
                dp[i][0] = cost
            }
            cost = dp[i-1][prev] + len(words[i])
            if words[i][len(words[i])-1] == l {
                cost--
            }
            if cost < dp[i][1] {
                dp[i][1] = cost
            }
        }
    }
    if dp[n-1][0] < dp[n-1][1] {
        return dp[n-1][0]
    }
    return dp[n-1][1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        int n = words.length;
        int[][] dp = new int[n][2];
        for (int[] row : dp) java.util.Arrays.fill(row, Integer.MAX_VALUE);
        dp[0][0] = dp[0][1] = words[0].length();
        for (int i = 1; i < n; i++) {
            for (int prev = 0; prev < 2; prev++) {
                char l = prev == 0 ? words[i-1].charAt(0) : words[i-1].charAt(words[i-1].length()-1);
                char r = prev == 0 ? words[i-1].charAt(words[i-1].length()-1) : words[i-1].charAt(0);
                int cost = dp[i-1][prev] + words[i].length();
                if (r == words[i].charAt(0)) cost--;
                dp[i][0] = Math.min(dp[i][0], cost);
                cost = dp[i-1][prev] + words[i].length();
                if (words[i].charAt(words[i].length()-1) == l) cost--;
                dp[i][1] = Math.min(dp[i][1], cost);
            }
        }
        return Math.min(dp[n-1][0], dp[n-1][1]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun minimizeConcatenatedLength(words: Array<String>): Int {
        val n = words.size
        val dp = Array(n) { IntArray(2) { Int.MAX_VALUE } }
        dp[0][0] = words[0].length
        dp[0][1] = words[0].length
        for (i in 1 until n) {
            for (prev in 0..1) {
                val l = if (prev == 0) words[i-1][0] else words[i-1].last()
                val r = if (prev == 0) words[i-1].last() else words[i-1][0]
                var cost = dp[i-1][prev] + words[i].length
                if (r == words[i][0]) cost--
                dp[i][0] = minOf(dp[i][0], cost)
                cost = dp[i-1][prev] + words[i].length
                if (words[i].last() == l) cost--
                dp[i][1] = minOf(dp[i][1], cost)
            }
        }
        return minOf(dp[n-1][0], dp[n-1][1])
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minimizeConcatenatedLength(self, words: list[str]) -> int:
        n: int = len(words)
        dp: list[list[int]] = [[float('inf')] * 2 for _ in range(n)]
        dp[0][0] = dp[0][1] = len(words[0])
        for i in range(1, n):
            for prev in (0, 1):
                l = words[i-1][0] if prev == 0 else words[i-1][-1]
                r = words[i-1][-1] if prev == 0 else words[i-1][0]
                cost = dp[i-1][prev] + len(words[i])
                if r == words[i][0]:
                    cost -= 1
                dp[i][0] = min(dp[i][0], cost)
                cost = dp[i-1][prev] + len(words[i])
                if words[i][-1] == l:
                    cost -= 1
                dp[i][1] = min(dp[i][1], cost)
        return min(dp[n-1][0], dp[n-1][1])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn minimize_concatenated_length(words: Vec<String>) -> i32 {
        let n = words.len();
        let mut dp = vec![[i32::MAX; 2]; n];
        dp[0][0] = words[0].len() as i32;
        dp[0][1] = words[0].len() as i32;
        for i in 1..n {
            for prev in 0..2 {
                let l = if prev == 0 { words[i-1].as_bytes()[0] } else { *words[i-1].as_bytes().last().unwrap() };
                let r = if prev == 0 { *words[i-1].as_bytes().last().unwrap() } else { words[i-1].as_bytes()[0] };
                let mut cost = dp[i-1][prev] + words[i].len() as i32;
                if r == words[i].as_bytes()[0] {
                    cost -= 1;
                }
                dp[i][0] = dp[i][0].min(cost);
                cost = dp[i-1][prev] + words[i].len() as i32;
                if *words[i].as_bytes().last().unwrap() == l {
                    cost -= 1;
                }
                dp[i][1] = dp[i][1].min(cost);
            }
        }
        dp[n-1][0].min(dp[n-1][1])
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    minimizeConcatenatedLength(words: string[]): number {
        const n = words.length;
        const dp = Array.from({length: n}, () => [Infinity, Infinity]);
        dp[0][0] = dp[0][1] = words[0].length;
        for (let i = 1; i < n; i++) {
            for (let prev = 0; prev < 2; prev++) {
                const l = prev === 0 ? words[i-1][0] : words[i-1][words[i-1].length-1];
                const r = prev === 0 ? words[i-1][words[i-1].length-1] : words[i-1][0];
                let cost = dp[i-1][prev] + words[i].length;
                if (r === words[i][0]) cost--;
                dp[i][0] = Math.min(dp[i][0], cost);
                cost = dp[i-1][prev] + words[i].length;
                if (words[i][words[i].length-1] === l) cost--;
                dp[i][1] = Math.min(dp[i][1], cost);
            }
        }
        return Math.min(dp[n-1][0], dp[n-1][1]);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of words, since we process each word and state in constant time.
  • 🧺 Space complexity: O(n), for the DP table.