# Solving Leetcode Interviews in Seconds with AI: Decremental String Concatenation # Introduction In this blog post, we will explore how to solve the LeetCode problem "2746" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months. # Problem Statement > 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 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.     Constraints: 1 <= words.length <= 1000 1 <= words[i].length <= 50 Each character in words[i] is an English lowercase letter # Explanation Here's a breakdown of the solution approach, followed by the Python code: * **Dynamic Programming:** Use dynamic programming to explore all possible join orders. The state will represent the current string's length and its starting and ending characters. * **State Definition:** The DP state `dp[i][start][end]` stores the minimum length achievable after processing the first `i+1` words (from `words[0]` to `words[i]`), where `start` is the first character and `end` is the last character of the resulting string. * **Transitions:** For each word at index `i`, consider joining it to the left or right of the previously formed string. Update the DP table with the minimum length obtained from both possibilities. * **Runtime Complexity:** O(n * 26 * 26) where n is the number of words. * **Storage Complexity:** O(n * 26 * 26) ```python def solve(): words = ["aa","ab","bc"] print(min_length(words)) words = ["ab","b"] print(min_length(words)) words = ["aaa","c","aba"] print(min_length(words)) def min_length(words): n = len(words) dp = {} def calculate_min_length(index, start_char, end_char): if index == n: return 0 if (index, start_char, end_char) in dp: return dp[(index, start_char, end_char)] word = words[index] word_start = word[0] word_end = word[-1] word_len = len(word) # Option 1: Join word to the right len1 = float('inf') join_len = word_len if end_char == word_start: join_len = word_len - 1 if index == 0: len1 = word_len + calculate_min_length(index + 1, word_start, word_end) else: len1 = join_len + calculate_min_length(index + 1, start_char, word_end) # Option 2: Join word to the left len2 = float('inf') join_len = word_len if word_end == start_char: join_len = word_len - 1 if index == 0: len2 = word_len + calculate_min_length(index + 1, word_start, word_end) else: len2 = join_len + calculate_min_length(index + 1, word_start, end_char) dp[(index, start_char, end_char)] = min(len1, len2) return dp[(index, start_char, end_char)] first_word = words[0] result = len(first_word) + calculate_min_length(1, first_word[0], first_word[-1]) dp = {} def calculate_min_length2(index, start_char, end_char): if index == n-1: return 0 if (index, start_char, end_char) in dp: return dp[(index, start_char, end_char)] word = words[index+1] word_start = word[0] word_end = word[-1] word_len = len(word) # Option 1: Join word to the right len1 = float('inf') join_len = word_len if end_char == word_start: join_len = word_len - 1 len1 = join_len + calculate_min_length2(index + 1, start_char, word_end) # Option 2: Join word to the left len2 = float('inf') join_len = word_len if word_end == start_char: join_len = word_len - 1 len2 = join_len + calculate_min_length2(index + 1, word_start, end_char) dp[(index, start_char, end_char)] = min(len1, len2) return dp[(index, start_char, end_char)] first_word = words[0] dp = {} result = len(first_word) + calculate_min_length2(0, first_word[0], first_word[-1]) return result # Code ```python def min_length(words): n = len(words) dp = {} def solve(index, first, last): if index == n: return 0 if (index, first, last) in dp: return dp[(index, first, last)] word = words[index] word_first = word[0] word_last = word[-1] word_len = len(word) # Join to the right right_cost = word_len if last == word_first: right_cost -= 1 right_res = right_cost + solve(index + 1, first, word_last) # Join to the left left_cost = word_len if word_last == first: left_cost -= 1 left_res = left_cost + solve(index + 1, word_first, last) dp[(index, first, last)] = min(right_res, left_res) return dp[(index, first, last)] first_word = words[0] result = len(first_word) + solve(1, first_word[0], first_word[-1]) return result ```