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:
stri = join(stri - 1, words[i])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 <= 10001 <= words[i].length <= 50words[i] is an English lowercase letterProblem Overview: You are given an array of strings. Starting from the first word, you can attach each next word either to the left or the right of the current string. If the boundary characters match, one character can be removed due to overlap. The goal is to minimize the final string length after processing all words.
Approach 1: Greedy Backtracking (Exponential Time)
This approach explores both choices for every word: attach it to the left or to the right of the current string. When concatenating, check whether the boundary characters match. If the last character of the left string equals the first character of the new word (or vice versa), reduce the resulting length by one due to overlap. Recursively try both placements and track the minimum possible final length. The algorithm effectively builds all valid concatenation orders while applying the overlap rule.
The downside is that each word introduces two branching decisions, producing up to 2^n states in the worst case. Time complexity is O(2^n) and space complexity is O(n) due to recursion depth. This method is useful for understanding the decision structure but becomes impractical as the number of words grows.
Approach 2: Dynamic Programming with Boundary States (O(n * 26 * 26))
The key observation is that the exact contents of the concatenated string do not matter. Only its first and last characters affect future overlaps. Instead of storing the full string, maintain a dynamic programming state dp[i][first][last] representing the minimum length after processing the first i words where the resulting string starts with character first and ends with last.
For each new word, compute two transitions. Attach the word to the right: compare the current ending character with the word's first character to see if an overlap reduces length by one. Attach the word to the left: compare the word's last character with the current starting character. Update the DP state with the new boundary characters accordingly. Because characters are lowercase English letters, there are only 26 × 26 boundary combinations.
This drastically reduces the state space. Instead of exploring all concatenated strings, the algorithm tracks only character boundaries. Time complexity becomes O(n * 26 * 26), effectively linear in the number of words. Space complexity is also O(26 * 26) when optimized with rolling arrays. This approach combines dynamic programming with character-state compression and works well for problems involving incremental string construction.
Recommended for interviews: The dynamic programming solution is the expected approach. A brute-force or backtracking explanation demonstrates understanding of the decision tree, but the DP formulation shows the key insight: only boundary characters matter. Interviewers often expect candidates to recognize this state compression technique, commonly used in string and array dynamic programming problems.
In this approach, we use dynamic programming to calculate the minimum length of strings possible for each step. We maintain a dynamic programming table dp[i][j], where i represents the index of the word we are processing, and j can be 0 or 1 indicating whether we put the current word on the left or right during the concatenation process. For each word, we calculate all possible lengths with respect to previous words and store the minimum possible length.
We initialize a DP table to store the minimum lengths for each concatenation possibility. Then, iterate through each word, calculating both possible join outcomes, updating the table with the minimum values found.
Time Complexity: O(n * max_len) where n is the number of words and max_len is the maximum length of a single word.
Space Complexity: O(n) for the DP table.
This approach uses a greedy method combined with backtracking to explore the sequence of join operations that minimize the resulting string length. The idea is to choose the better of the two options at each step (joining the current new word from the left or the right) by simulating both and choosing the one that yields a shorter string.
In this solution, utilize backtracking to simulate different join operations. At each step, the method tries both concatenation orders and uses recursion to explore both paths, returning the minimum length found.
Java
JavaScript
Time Complexity: O(n * 2^n) in the worst case where n is the number of words, due to exploring all combinatorial possibilities.
Space Complexity: O(n) due to recursive call stack.
We notice that when concatenating strings, the first and last characters of the string will affect the length of the concatenated string. Therefore, we design a function dfs(i, a, b), which represents the minimum length of the concatenated string starting from the i-th string, and the first character of the previously concatenated string is a, and the last character is b.
The execution process of the function dfs(i, a, b) is as follows:
i = n, it means that all strings have been concatenated, return 0;i-th string to the end or the beginning of the already concatenated string, and get the lengths x and y of the concatenated string, then dfs(i, a, b) = min(x, y) + |words[i]|.To avoid repeated calculations, we use the method of memoization search. Specifically, we use a three-dimensional array f to store all the return values of dfs(i, a, b). When we need to calculate dfs(i, a, b), if f[i][a][b] has been calculated, we directly return f[i][a][b]; otherwise, we calculate the value of dfs(i, a, b) according to the above recurrence relation, and store it in f[i][a][b].
In the main function, we directly return |words[0]| + dfs(1, words[0][0], words[0][|words[0]| - 1]).
The time complexity is O(n times C^2), and the space complexity is O(n times C^2). Where C represents the maximum length of the string.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * max_len) where n is the number of words and max_len is the maximum length of a single word. |
| Greedy Backtracking Approach | Time Complexity: O(n * 2^n) in the worst case where n is the number of words, due to exploring all combinatorial possibilities. |
| Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Backtracking | O(2^n) | O(n) | Useful for understanding the decision tree or when input size is very small |
| Dynamic Programming with Boundary States | O(n * 26 * 26) | O(26 * 26) | Optimal approach for large inputs; tracks only first and last characters of the constructed string |
Leetcode BiWeekly contest 107 - Medium - Decremental String Concatenation • Prakhar Agrawal • 1,128 views views
Watch 6 more video solutions →Practice Decremental String Concatenation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor