Skip to content

2746. Decremental String Concatenation

SourceBiweekly Contest 107 Q3DifficultyMediumRating2126

Description

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

Solutions

Thinking

Words must be prepended or appended in order; equal touching letters collapse into one, and we want the shortest final length. Two choices per word at \(n\le 1000\) make a raw search impossible.

The future cost depends only on the current first and last letters. \(dfs(i,a,b)\) is the extra length from word \(i\) with ends \(a,b\): append compares \(s[0]\) with \(b\), prepend compares \(s[-1]\) with \(a\). Memoization yields \(O(n\cdot 26^2)\) states.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        @cache
        def dfs(i: int, a: str, b: str) -> int:
            if i >= len(words):
                return 0
            s = words[i]
            x = dfs(i + 1, a, s[-1]) - int(s[0] == b)
            y = dfs(i + 1, s[0], b) - int(s[-1] == a)
            return len(s) + min(x, y)

        return len(words[0]) + dfs(1, words[0][0], words[0][-1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        int f[n][26][26];
        memset(f, 0, sizeof(f));
        function<int(int, int, int)> dfs = [&](int i, int a, int b) {
            if (i >= n) {
                return 0;
            }
            if (f[i][a][b]) {
                return f[i][a][b];
            }
            auto s = words[i];
            int m = s.size();
            int x = dfs(i + 1, a, s[m - 1] - 'a') - (s[0] - 'a' == b);
            int y = dfs(i + 1, s[0] - 'a', b) - (s[m - 1] - 'a' == a);
            return f[i][a][b] = m + min(x, y);
        };
        return words[0].size() + dfs(1, words[0].front() - 'a', words[0].back() - 'a');
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func minimizeConcatenatedLength(words []string) int {
    n := len(words)
    f := make([][26][26]int, n)
    var dfs func(i, a, b int) int
    dfs = func(i, a, b int) int {
        if i >= n {
            return 0
        }
        if f[i][a][b] > 0 {
            return f[i][a][b]
        }
        s := words[i]
        m := len(s)
        x := dfs(i+1, a, int(s[m-1]-'a'))
        y := dfs(i+1, int(s[0]-'a'), b)
        if int(s[0]-'a') == b {
            x--
        }
        if int(s[m-1]-'a') == a {
            y--
        }
        f[i][a][b] = m + min(x, y)
        return f[i][a][b]
    }
    return len(words[0]) + dfs(1, int(words[0][0]-'a'), int(words[0][len(words[0])-1]-'a'))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function minimizeConcatenatedLength(words: string[]): number {
    const n = words.length;
    const f: number[][][] = Array(n)
        .fill(0)
        .map(() =>
            Array(26)
                .fill(0)
                .map(() => Array(26).fill(0)),
        );
    const dfs = (i: number, a: number, b: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i][a][b] > 0) {
            return f[i][a][b];
        }
        const s = words[i];
        const m = s.length;
        const x =
            dfs(i + 1, a, s[m - 1].charCodeAt(0) - 97) - (s[0].charCodeAt(0) - 97 === b ? 1 : 0);
        const y =
            dfs(i + 1, s[0].charCodeAt(0) - 97, b) - (s[m - 1].charCodeAt(0) - 97 === a ? 1 : 0);
        return (f[i][a][b] = Math.min(x + m, y + m));
    };
    return (
        words[0].length +
        dfs(1, words[0][0].charCodeAt(0) - 97, words[0][words[0].length - 1].charCodeAt(0) - 97)
    );
}

Solution 2: Dynamic Programming

Thinking

Each word is attached to the left or the right, and equal letters that meet count once. There can be \(1000\) words, and trying the right side first always moves to the next index, so the search has depth \(n\). Only the current first and last letters affect later choices. Let \(f[i][a][b]\) be the extra length from word \(i\) with those ends, set \(f[n]\) to \(0\), and fill decreasing \(i\) over every pair of ends.

Let \(f[i][a][b]\) be the shortest extra length when connecting from word \(i\), with the string so far starting with \(a\) and ending with \(b\). The boundary is \(f[n][a][b]=0\). For \(i\) from \(n-1\) down to \(1\), and for every pair of ends \(a,b\), try both sides. Appending \(words[i]\) saves one character when its first character equals \(b\), and the new end is its last character. Prepending saves one character when its last character equals \(a\), and the new start is its first character. \(f[i][a][b]\) is the shorter of those two lengths plus \(|words[i]|\). The answer is \(|words[0]| + f[1][words[0][0]][words[0][|words[0]|-1]]\).

The time complexity is \(O(n \times |\Sigma|^2)\), and the space complexity is \(O(n \times |\Sigma|^2)\). Here, \(n\) is the number of words, and \(|\Sigma|\) is the alphabet size, which is \(26\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        n = len(words)
        f = [[[0] * 26 for _ in range(26)] for _ in range(n + 1)]
        for i in range(n - 1, 0, -1):
            s = words[i]
            m = len(s)
            c, d = ord(s[0]) - 97, ord(s[-1]) - 97
            for a in range(26):
                for b in range(26):
                    x = f[i + 1][a][d] - (c == b)
                    y = f[i + 1][c][b] - (d == a)
                    f[i][a][b] = m + min(x, y)
        a, b = ord(words[0][0]) - 97, ord(words[0][-1]) - 97
        return len(words[0]) + f[1][a][b]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        int n = words.length;
        int[][][] f = new int[n + 1][26][26];
        for (int i = n - 1; i > 0; --i) {
            String s = words[i];
            int m = s.length();
            int c = s.charAt(0) - 'a';
            int d = s.charAt(m - 1) - 'a';
            for (int a = 0; a < 26; ++a) {
                for (int b = 0; b < 26; ++b) {
                    int x = f[i + 1][a][d] - (c == b ? 1 : 0);
                    int y = f[i + 1][c][b] - (d == a ? 1 : 0);
                    f[i][a][b] = m + Math.min(x, y);
                }
            }
        }
        int a = words[0].charAt(0) - 'a';
        int b = words[0].charAt(words[0].length() - 1) - 'a';
        return words[0].length() + f[1][a][b];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(26, vector<int>(26)));
        for (int i = n - 1; i > 0; --i) {
            auto& s = words[i];
            int m = s.size();
            int c = s[0] - 'a';
            int d = s[m - 1] - 'a';
            for (int a = 0; a < 26; ++a) {
                for (int b = 0; b < 26; ++b) {
                    int x = f[i + 1][a][d] - (c == b);
                    int y = f[i + 1][c][b] - (d == a);
                    f[i][a][b] = m + min(x, y);
                }
            }
        }
        int a = words[0].front() - 'a';
        int b = words[0].back() - 'a';
        return words[0].size() + f[1][a][b];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func minimizeConcatenatedLength(words []string) int {
    n := len(words)
    f := make([][26][26]int, n+1)
    for i := n - 1; i > 0; i-- {
        s := words[i]
        m := len(s)
        c := int(s[0] - 'a')
        d := int(s[m-1] - 'a')
        for a := 0; a < 26; a++ {
            for b := 0; b < 26; b++ {
                x := f[i+1][a][d]
                y := f[i+1][c][b]
                if c == b {
                    x--
                }
                if d == a {
                    y--
                }
                f[i][a][b] = m + min(x, y)
            }
        }
    }
    a := int(words[0][0] - 'a')
    b := int(words[0][len(words[0])-1] - 'a')
    return len(words[0]) + f[1][a][b]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function minimizeConcatenatedLength(words: string[]): number {
    const n = words.length;
    const f: number[][][] = Array.from({ length: n + 1 }, () =>
        Array.from({ length: 26 }, () => Array(26).fill(0)),
    );
    for (let i = n - 1; i > 0; --i) {
        const s = words[i];
        const m = s.length;
        const c = s.charCodeAt(0) - 97;
        const d = s.charCodeAt(m - 1) - 97;
        for (let a = 0; a < 26; ++a) {
            for (let b = 0; b < 26; ++b) {
                const x = f[i + 1][a][d] - (c === b ? 1 : 0);
                const y = f[i + 1][c][b] - (d === a ? 1 : 0);
                f[i][a][b] = m + Math.min(x, y);
            }
        }
    }
    const a = words[0].charCodeAt(0) - 97;
    const b = words[0].charCodeAt(words[0].length - 1) - 97;
    return words[0].length + f[1][a][b];
}

Comments