2746. Decremental String Concatenation

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 str₀ = words[0]. Starting from i = 1 up to i = n - 1, for the i^th operation, you can do one of the following:

Make str_i = join(str_{i - 1}, words[i])
Make str_i = join(words[i], str_{i - 1})

Your task is to minimize the length of str_{n - 1}.

Return an integer denoting the minimum possible length of str_{n - 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 str₂: 
str₀ = "aa"
str₁ = join(str₀, "ab") = "aab"
str₂ = join(str₁, "bc") = "aabc" 
It can be shown that the minimum possible length of str₂ is 4.

Example 2:

Input: words = ["ab","b"]
Output: 2
Explanation: In this example, str₀ = "ab", there are two ways to get str₁: 
join(str₀, "b") = "ab" or join("b", str₀) = "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 str₂: 
str₀ = "aaa"
str₁ = join(str₀, "c") = "aaac"
str₂ = join("aba", str₁) = "abaaac"
It can be shown that the minimum possible length of str₂ is 6.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 50
Each character in words[i] is an English lowercase letter

Solutions

Solution 1: 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.

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.

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);
    }
}


// Solution 2
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];
    }
}

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');
    }
};


// Solution 2
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];
    }
};

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])



# Solution 2
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]

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'))
}


// Solution 2
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]
}

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
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];
}

2746 - Decremental String Concatenation

2746. Decremental String Concatenation

Description

Solutions

Solution 2: Dynamic Programming

All Problems

All Solutions

Welcome to Subscribe On Youtube

2746. Decremental String Concatenation

Description

Solutions

Solution 2: Dynamic Programming

All Problems

All Solutions