Scale Engineer

Decremental String Concatenation

Med
#2471Time: O(N * C^3), where N is the number of words and C is the alphabet size (26). For each state `(i, f, l)`, we iterate through C possible previous characters.Space: O(N * C^2), where N is the number of words and C is the alphabet size (26). This is for the memoization table.
Patterns
Dynamic Programming
Data structures
ArrayString

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses recursion with memoization to solve the problem. It explores all possible ways of joining the strings and stores the results of subproblems to avoid redundant calculations. The state of our recursive function is defined by the index of the current word being processed, and the first and last characters of the string formed so far.

Algorithm

  • Create a 3D memoization table memo[n][26][26] initialized with a value indicating "not computed".
  • Define a recursive function solve(i, first, last) that computes the minimum length of a string formed from words[0...i] starting with first and ending with last.
  • Base Case: If i == 0, the function returns words[0].length() if first and last match the boundaries of words[0], otherwise, it returns a value representing infinity.
  • Recursive Step: For solve(i, first, last), check the memoization table. If the value is not computed, calculate it by considering two cases:
    1. The string was formed by join(str_{i-1}, words[i]). This is possible if last equals the last character of words[i]. We recursively call solve(i-1, first, prev_last) for all possible prev_last characters ('a' through 'z') and find the minimum length.
    2. The string was formed by join(words[i], str_{i-1}). This is possible if first equals the first character of words[i]. We recursively call solve(i-1, prev_first, last) for all possible prev_first characters and find the minimum length.
  • Store the computed minimum length in the memoization table and return it.
  • The final answer is the minimum value returned by solve(n-1, f, l) over all possible characters f and l.

Walkthrough

We define a recursive function, say solve(i, firstChar, lastChar), which calculates the minimum length of a string formed by joining words[0] through words[i] that starts with firstChar and ends with lastChar. The state is (i, firstChar, lastChar), representing the subproblem for words[0...i]. We use a 3D array memo[i][firstChar - 'a'][lastChar - 'a'] to store the results.

Base Case: For i = 0, the string is just words[0]. The length is words[0].length(), and the first and last characters are fixed. For any other combination of first/last characters, the length is considered infinite.

Recursive Step: To compute solve(i, f, l), we consider how a string with first char f and last char l could have been formed at step i. There are two possibilities for the i-th join operation:

  1. str_i = join(str_{i-1}, words[i]): The new first character f must be the same as the first character of str_{i-1}, and the new last character l must be the last character of words[i]. We iterate through all possible last characters of str_{i-1} to find the minimum length.
  2. str_i = join(words[i], str_{i-1}): The new first character f must be the first character of words[i], and the new last character l must be the same as the last character of str_{i-1}. We iterate through all possible first characters of str_{i-1}.

The function returns the minimum length found. The final answer is the minimum value among solve(n-1, f, l) for all possible f and l.

class Solution {    private Integer[][][] memo;    private String[] words;    private int n;    private final int INF = 1_000_000_000;     public int minimizeConcatenatedLength(String[] words) {        this.words = words;        this.n = words.length;        if (n == 1) {            return words[0].length();        }        this.memo = new Integer[n][26][26];         int minLength = INF;        for (char first = 'a'; first <= 'z'; first++) {            for (char last = 'a'; last <= 'z'; last++) {                minLength = Math.min(minLength, solve(n - 1, first, last));            }        }        return minLength;    }     private int solve(int i, char first, char last) {        if (i == 0) {            String w = words[0];            if (w.charAt(0) == first && w.charAt(w.length() - 1) == last) {                return w.length();            }            return INF;        }         if (memo[i][first - 'a'][last - 'a'] != null) {            return memo[i][first - 'a'][last - 'a'];        }         int minLen = INF;        String w = words[i];        char wFirst = w.charAt(0);        char wLast = w.charAt(w.length() - 1);        int wLen = w.length();         // Case 1: str_i = join(str_{i-1}, words[i])        if (last == wLast) {            for (char prevLast = 'a'; prevLast <= 'z'; prevLast++) {                int prevLen = solve(i - 1, first, prevLast);                if (prevLen != INF) {                    int currentLen = prevLen + wLen - (prevLast == wFirst ? 1 : 0);                    minLen = Math.min(minLen, currentLen);                }            }        }         // Case 2: str_i = join(words[i], str_{i-1})        if (first == wFirst) {            for (char prevFirst = 'a'; prevFirst <= 'z'; prevFirst++) {                int prevLen = solve(i - 1, prevFirst, last);                if (prevLen != INF) {                    int currentLen = prevLen + wLen - (wLast == prevFirst ? 1 : 0);                    minLen = Math.min(minLen, currentLen);                }            }        }         return memo[i][first - 'a'][last - 'a'] = minLen;    }}

Complexity

Time

O(N * C^3), where N is the number of words and C is the alphabet size (26). For each state `(i, f, l)`, we iterate through C possible previous characters.

Space

O(N * C^2), where N is the number of words and C is the alphabet size (26). This is for the memoization table.

Trade-offs

Pros

  • Conceptually straightforward, as it directly translates the recursive structure of the problem.

  • Avoids recomputing solutions to the same subproblem through memoization.

Cons

  • Higher time complexity compared to the bottom-up approach due to an extra loop over the alphabet in the recursive step.

  • Can lead to stack overflow for very deep recursion, although the constraint n <= 1000 is generally manageable.

  • Uses more space than the optimized bottom-up approach.

Solutions

class Solution {private  Integer[][][] f;private  String[] words;private  int n;public  int minimizeConcatenatedLength(String[] words) {    n = words.length;    this.words = words;    f = new Integer[n][26][26];    return words[0].length() +           dfs(1, words[0].charAt(0) - 'a',               words[0].charAt(words[0].length() - 1) - 'a');  }private  int dfs(int i, int a, int b) {    if (i >= n) {      return 0;    }    if (f[i][a][b] != null) {      return f[i][a][b];    }    String s = words[i];    int m = s.length();    int x =        dfs(i + 1, a, s.charAt(m - 1) - 'a') - (s.charAt(0) - 'a' == b ? 1 : 0);    int y =        dfs(i + 1, s.charAt(0) - 'a', b) - (s.charAt(m - 1) - 'a' == a ? 1 : 0);    return f[i][a][b] = m + Math.min(x, y);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem