LeetCode in Kotlin

2746. Decremental String Concatenation

Medium

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

Solution

class Solution {
    private val inf = 1e9.toInt()
    private lateinit var dp: Array<Array<Array<Int?>>>

    fun minimizeConcatenatedLength(words: Array<String>): Int {
        val n = words.size
        dp = Array(n) {
            Array(26) {
                arrayOfNulls(
                    26,
                )
            }
        }
        val curWord = words[0]
        val curLen = curWord.length
        val curFirst = curWord[0]
        val curLast = curWord[curLen - 1]
        return curLen + solve(1, curFirst, curLast, n, words)
    }

    private fun solve(idx: Int, prevFirst: Char, prevLast: Char, n: Int, words: Array<String>): Int {
        if (idx == n) return 0
        if (dp[idx][prevFirst.code - 'a'.code][prevLast.code - 'a'.code] != null) {
            return dp[idx][prevFirst.code - 'a'.code][prevLast.code - 'a'.code]!!
        }
        val curWord = words[idx]
        val curLen = curWord.length
        val curFirst = curWord[0]
        val curLast = curWord[curLen - 1]
        var ans = inf
        ans = if (prevFirst == curLast) {
            ans.coerceAtMost(curLen - 1 + solve(idx + 1, curFirst, prevLast, n, words))
        } else {
            ans.coerceAtMost(curLen + solve(idx + 1, curFirst, prevLast, n, words))
        }
        ans = if (prevLast == curFirst) {
            ans.coerceAtMost(curLen - 1 + solve(idx + 1, prevFirst, curLast, n, words))
        } else {
            ans.coerceAtMost(curLen + solve(idx + 1, prevFirst, curLast, n, words))
        }
        return ans.also { dp[idx][prevFirst.code - 'a'.code][prevLast.code - 'a'.code] = it }
    }
}

This site is open source. Improve this page.