Problem statement

https://binarysearch.com/problems/Longest-Concatenated-String/

Solution

Let dp[i, j] be the answer when we traversed several words and it is the longest length which starts with i and ends with j. Then when we get new word [beg, end], we can try to attach it to all words with [i, beg] + [beg, end] to update [i, end].

Complexity

It is O(n*k^2) for time and O(k^2) for space, where k = 26 is the size of alphabet

Code

class Solution:
    def solve(self, words):
        alph = string.ascii_lowercase

        n = len(words)
        dp = Counter()

        for word in words:
            beg, end = word[0], word[-1]
            for i in alph:
                if dp[i, beg]:
                    dp[i, end] = max(dp[i, end], dp[i, beg] + len(word))

            dp[beg, end] = max(dp[beg, end], len(word))

        return max(dp[c, c] for c in alph)