#2746
Decremental String Concatenation
expert · 1140 · lc medium +32 · verified · 27.5% accepted · 375 likes · top 5%
Description
Given a 0-indexed words array of n strings, define join(x, y) as concatenation of x and y where if x's last character equals y's first character, one copy of that character is dropped. Starting from str0 = words[0], at each step i you may either append or prepend words[i] via join. Return the minimum possible length of the final string.
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.
Code
1
2
3