Decremental String Concatenation
MediumUpdated: Aug 2, 2025
Practice on:
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
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 <= 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
- Let
nbe the number of words. - Define
dp[i][0]as the minimum length after processing the firstiwords, ending with thei-1th word on the left;dp[i][1]for ending with thei-1th word on the right. - Initialize
dp[0][0] = dp[0][1] = len(words[0]). - For each
ifrom 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).
- The answer is the minimum of the two states after all words are processed.
Code
C++
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]);
}
};
Go
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]
}
Java
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]);
}
}
Kotlin
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])
}
}
Python
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])
Rust
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])
}
}
TypeScript
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), wherenis the number of words, since we process each word and state in constant time. - 🧺 Space complexity:
O(n), for the DP table.