Skip to main content
Talentd

Decremental String Concatenation - Solution & Explanation

MediumArrayStringDynamic Programming16 min read
Practice this problem

Problem Statement

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

Approach Overview

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

Approach 1: Dynamic Programming Approach

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Backtracking Approach

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Memoization Search

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:

  • If i = n, it means that all strings have been concatenated, return 0;
  • Otherwise, we consider concatenating the 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) for the DP table.

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.
Space Complexity: O(n) due to recursive call stack.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy BacktrackingO(2^n)O(n)Useful for understanding the decision tree or when input size is very small
Dynamic Programming with Boundary StatesO(n * 26 * 26)O(26 * 26)Optimal approach for large inputs; tracks only first and last characters of the constructed string

Video Solution

Leetcode BiWeekly contest 107 - Medium - Decremental String Concatenation • Prakhar Agrawal • 1,131 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Decremental String Concatenation easy or hard?
Decremental String Concatenation is rated Medium on LeetCode with an acceptance rate around 27%. The challenge comes from recognizing that only boundary characters matter, enabling a compressed dynamic programming state instead of storing full strings.
Decremental String Concatenation Python/Java solution
Python and C++ implementations typically use memoized or iterative dynamic programming over boundary characters. Java and JavaScript solutions often demonstrate a recursive backtracking approach first, then optimize using DP to avoid exponential branching.
How to solve Decremental String Concatenation in O(n)?
Track only the first and last characters of the constructed string using dynamic programming. For each word, compute two transitions: attach the word to the left or right. Because there are only 26 letters, the DP state size is fixed, making the effective complexity O(n * 26 * 26), which behaves like O(n) for practical constraints.
What is the best approach for Decremental String Concatenation?
Dynamic programming with boundary character states is the best approach. Instead of storing full concatenated strings, track only the first and last characters after processing each word. This reduces the state space to 26 × 26 possibilities and results in O(n * 26 * 26) time complexity.
Is Decremental String Concatenation asked at Google/Amazon/Meta?
Problems combining dynamic programming with string manipulation frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that track boundary characters or compress DP state are common in mid-level algorithm interviews.
What data structure is used in Decremental String Concatenation?
The optimal solution uses dynamic programming tables indexed by character boundaries. Each state represents the minimum length for a string with a specific starting and ending character after processing a prefix of the words array.
What is the time complexity of Decremental String Concatenation?
The optimal dynamic programming solution runs in O(n * 26 * 26) time, where n is the number of words and 26 represents possible lowercase boundary characters. Space complexity can be reduced to O(26 * 26) by storing only current boundary states.

Ready to solve this problem?

Practice Decremental String Concatenation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest Merge Of Two Strings