Decremental String Concatenation

Medium
1636.

Decremental String Concatenation

Decremental String Concatenation is a medium coding problem on arrays, strings and dynamic programming, asked in Amazon interviews.

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 <= 1000
  • 1 <= words[i].length <= 50
  • words[i] consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {number}
 */
var minimizeConcatenatedLength = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 1 <= words[i].length <= 50
  • words[i] consists of lowercase English letters

Hints for Decremental String Concatenation

  1. Hint 1

    Whatever happens in the middle of the string never matters again — only its first and last characters affect future joins.

  2. Hint 2

    So the state after i words is (first char, last char) with the shortest length that reaches it: at most 26 × 26 states.

  3. Hint 3

    Appending word w to 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

  1. Initialise dp[a][b] = ∞, then dp[words[0][0]][words[0][last]] = |words[0]|.
  2. For each next word w with first letter f, last letter l and length L, build a new table: from each finite dp[a][b], relax new[a][l] with dp[a][b] + L - (b == f) and new[f][b] with dp[a][b] + L - (l == a).
  3. 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings