Decremental String Concatenation — Problem & Solution
Decremental String Concatenation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Decremental String Concatenation is a medium coding problem on arrays, strings and dynamic programming, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Dynamic Programming
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Define join(x, y) as the concatenation xy, except that when the last character of x equals the first character of y, one of those two characters is dropped. For example join("ab", "ba") = "aba" and join("ab", "cde") = "abcde".
You are given n strings words. Start with str_0 = words[0]. For each i from 1 to n - 1, choose either str_i = join(str_(i-1), words[i]) or str_i = join(words[i], str_(i-1)).
Return the minimum possible length of str_(n-1).
Example 1
Input: words = ["aa","ab","bc"]
Output: 4
Explanation: join("aa","ab") = "aab", then join("aab","bc") = "aabc".
Example 2
Input: words = ["ab","b"]
Output: 2
Explanation: join("ab","b") = "ab".
Example 3
Input: words = ["aaa","c","aba"]
Output: 6
Explanation: "aaac" then join("aba","aaac") = "abaaac".
Constraints
1 <= words.length <= 10001 <= words[i].length <= 50words[i] consists of lowercase English letters
Hints for Decremental String Concatenation
Hint 1
Whatever happens in the middle of the string never matters again — only its first and last characters affect future joins.
Hint 2
So the state after
iwords is(first char, last char)with the shortest length that reaches it: at most26 × 26states.Hint 3
Appending word
wto state(a, b)gives(a, w.last)with length+|w| - [b == w.first]; prepending gives(w.first, b)with length+|w| - [w.last == a].
How to solve Decremental String Concatenation
The only information about the built string that future joins use is its first and last character, so a DP over those two letters, keeping the minimum length for each pair, captures every choice sequence.
Approach
- Initialise
dp[a][b] = ∞, thendp[words[0][0]][words[0][last]] = |words[0]|. - For each next word
wwith first letterf, last letterland lengthL, build a new table: from each finitedp[a][b], relaxnew[a][l]withdp[a][b] + L - (b == f)andnew[f][b]withdp[a][b] + L - (l == a). - After the last word, return the minimum over the table.
Why it works
Two partial strings with the same first and last characters behave identically for every later join, so keeping only the shorter one never loses the optimum. Every sequence of left/right choices is represented by the transitions, so the minimum of the final table is the answer.
Complexity
- Time —
O(n · 26²) - Space —
O(26²)
Pitfalls
- A one-character word has the same first and last letter — both overlaps can apply to it in different steps.
- Only one character is removed per join, even if both ends match.
- Tracking the whole string (or only its length) is not enough — the ends are what matter.
Reference solution
Python
from typing import List
def minimizeConcatenatedLength(words: List[str]) -> int:
INF = float('inf')
dp = [[INF] * 26 for _ in range(26)]
w0 = words[0]
dp[ord(w0[0]) - 97][ord(w0[-1]) - 97] = len(w0)
for w in words[1:]:
f, l, L = ord(w[0]) - 97, ord(w[-1]) - 97, len(w)
nd = [[INF] * 26 for _ in range(26)]
for a in range(26):
row = dp[a]
for b in range(26):
cur = row[b]
if cur == INF:
continue
v = cur + L - (1 if b == f else 0)
if v < nd[a][l]:
nd[a][l] = v
v = cur + L - (1 if l == a else 0)
if v < nd[f][b]:
nd[f][b] = v
dp = nd
return min(min(row) for row in dp)Java
public static int minimizeConcatenatedLength(String[] words) {
final int INF = Integer.MAX_VALUE / 2;
int[] dp = new int[676];
Arrays.fill(dp, INF);
String w0 = words[0];
dp[(w0.charAt(0) - 'a') * 26 + (w0.charAt(w0.length() - 1) - 'a')] = w0.length();
for (int i = 1; i < words.length; i++) {
String w = words[i];
int f = w.charAt(0) - 'a', l = w.charAt(w.length() - 1) - 'a', L = w.length();
int[] nd = new int[676];
Arrays.fill(nd, INF);
for (int a = 0; a < 26; a++) {
for (int b = 0; b < 26; b++) {
int cur = dp[a * 26 + b];
if (cur == INF) continue;
nd[a * 26 + l] = Math.min(nd[a * 26 + l], cur + L - (b == f ? 1 : 0));
nd[f * 26 + b] = Math.min(nd[f * 26 + b], cur + L - (l == a ? 1 : 0));
}
}
dp = nd;
}
int best = INF;
for (int v : dp) best = Math.min(best, v);
return best;
}C++
int minimizeConcatenatedLength(vector<string>& words) {
const int INF = INT_MAX / 2;
vector<int> dp(676, INF);
const string& w0 = words[0];
dp[(w0.front() - 'a') * 26 + (w0.back() - 'a')] = w0.size();
for (size_t i = 1; i < words.size(); i++) {
const string& w = words[i];
int f = w.front() - 'a', l = w.back() - 'a', L = w.size();
vector<int> nd(676, INF);
for (int a = 0; a < 26; a++) {
for (int b = 0; b < 26; b++) {
int cur = dp[a * 26 + b];
if (cur == INF) continue;
nd[a * 26 + l] = min(nd[a * 26 + l], cur + L - (b == f ? 1 : 0));
nd[f * 26 + b] = min(nd[f * 26 + b], cur + L - (l == a ? 1 : 0));
}
}
dp = nd;
}
return *min_element(dp.begin(), dp.end());
}JavaScript
var minimizeConcatenatedLength = function(words) {
var INF = 1e9, dp = new Array(676).fill(INF), w0 = words[0];
dp[(w0.charCodeAt(0) - 97) * 26 + w0.charCodeAt(w0.length - 1) - 97] = w0.length;
for (var i = 1; i < words.length; i++) {
var w = words[i], f = w.charCodeAt(0) - 97, l = w.charCodeAt(w.length - 1) - 97, L = w.length;
var nd = new Array(676).fill(INF);
for (var a = 0; a < 26; a++) {
for (var b = 0; b < 26; b++) {
var cur = dp[a * 26 + b];
if (cur === INF) continue;
var v = cur + L - (b === f ? 1 : 0);
if (v < nd[a * 26 + l]) nd[a * 26 + l] = v;
v = cur + L - (l === a ? 1 : 0);
if (v < nd[f * 26 + b]) nd[f * 26 + b] = v;
}
}
dp = nd;
}
var best = INF;
for (var k = 0; k < 676; k++) if (dp[k] < best) best = dp[k];
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.