2746. Decremental String Concatenation Medium

1/**
2 * [2746] Decremental String Concatenation
3 *
4 * You are given a 0-indexed array words containing n strings.
5 * 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.
6 * For example join("ab", "ba") = "aba" and join("ab", "cde") = "abcde".
7 * You are to perform n - 1 join operations. Let str0 = words[0]. Starting from i = 1 up to i = n - 1, for the i^th operation, you can do one of the following:
8 * 
9 * 	Make stri = join(stri - 1, words[i])
10 * 	Make stri = join(words[i], stri - 1)
11 * 
12 * Your task is to minimize the length of strn - 1.
13 * Return an integer denoting the minimum possible length of strn - 1.
14 *  
15 * <strong class="example">Example 1:
16 * 
17 * Input: words = ["aa","ab","bc"]
18 * Output: 4
19 * Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: 
20 * str0 = "aa"
21 * str1 = join(str0, "ab") = "aab"
22 * str2 = join(str1, "bc") = "aabc" 
23 * It can be shown that the minimum possible length of str2 is 4.
24 * <strong class="example">Example 2:
25 * 
26 * Input: words = ["ab","b"]
27 * Output: 2
28 * Explanation: In this example, str0 = "ab", there are two ways to get str1: 
29 * join(str0, "b") = "ab" or join("b", str0) = "bab". 
30 * The first string, "ab", has the minimum length. Hence, the answer is 2.
31 * 
32 * <strong class="example">Example 3:
33 * 
34 * Input: words = ["aaa","c","aba"]
35 * Output: 6
36 * Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: 
37 * str0 = "aaa"
38 * str1 = join(str0, "c") = "aaac"
39 * str2 = join("aba", str1) = "abaaac"
40 * It can be shown that the minimum possible length of str2 is 6.
41 * 
42 * <div class="notranslate" style="all: initial;"> </div>
43 *  
44 * Constraints:
45 * 
46 * 	1 <= words.length <= 1000
47 * 	1 <= words[i].length <= 50
48 * 	Each character in words[i] is an English lowercase letter
49 * 
50 */
51pub struct Solution {}
52
53// problem: https://leetcode.com/problems/decremental-string-concatenation/
54// discuss: https://leetcode.com/problems/decremental-string-concatenation/discuss/?currentPage=1&orderBy=most_votes&query=
55
56// submission codes start here
57
58impl Solution {
59    pub fn minimize_concatenated_length(words: Vec<String>) -> i32 {
60        0
61    }
62}
63
64// submission codes end
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_2746() {
72    }
73}
74